# Git4Voc: Git-based Versioning for Collaborative Vocabulary Development

Lavdim Halilaj  EIS Department
University of Bonn
Bonn, Germany
<EMAIL_ADDRESS>Irlán Grangel-González  EIS Department
University of Bonn
Bonn, Germany
<EMAIL_ADDRESS>Gökhan Coskun  EIS Department
University of Bonn
Bonn, Germany
<EMAIL_ADDRESS>Sören Auer  EIS Department
University of Bonn
Bonn, Germany
<EMAIL_ADDRESS>
###### Abstract

Collaborative vocabulary development in the context of data integration is the
process of finding consensus between the experts of the different systems and
domains. The complexity of this process is increased with the number of
involved people, the variety of the systems to be integrated and the dynamics
of their domain. In this paper we advocate that the realization of a powerful
version control system is the heart of the problem. Driven by this idea and
the success of Git in the context of software development, we investigate the
applicability of Git for collaborative vocabulary development. Even though
vocabulary development and software development have much more similarities
than differences there are still important differences. These need to be
considered within the development of a successful versioning and collaboration
system for vocabulary development. Therefore, this paper starts by presenting
the challenges we were faced with during the creation of vocabularies
collaboratively and discusses its distinction to software development. Based
on these insights we propose Git4Voc which comprises guidelines how Git can be
adopted to vocabulary development. Finally, we demonstrate how Git hooks can
be implemented to go beyond the plain functionality of Git by realizing
vocabulary-specific features like syntactic validation and semantic diffs.

###### Index Terms:

version control system; collaborative vocabulary development; git;

##  I Introduction

One of the key obstacles for the wider deployment of semantic technologies is
the lack of comprehensive vocabularies. This is because vocabulary development
requires a significant investment, which is difficult to make by a single
person or organisation. If we look at current vocabularies (e.g.
LOV111http://lov.okfn.org), we observe that they are rather simplistic. For a
total of 457 vocabularies listed in LOV, a straightforward query against the
LOV SPARQL endpoint tells us that the average number of classes for each
vocabulary is 42 whereas the average number of properties is 59. Omitting the
four vocabularies with the highest number of classes and properties, these
figures decrease to 31 classes and 37 properties on average. We also observe
that a large number of crucial domains is not or only superficially covered by
existing vocabularies. One of the main reasons for the lack of vocabularies is
also the lack of adequate methodological and tool support.

At the same time, the problem of integrating data from different systems
receives ever-increasing attention. Identifying the main terms across
heterogeneous data sources by finding a consensus between the developers and
defining a shared vocabulary is an effective approach to tackle this problem.
However, this process, which we refer to as _collaborative vocabulary
development_ , itself is a complex problem to be solved. In fact, the main
challenge for the vocabulary engineers is to work collaboratively on a shared
objective in a harmonic and efficient way while avoiding misunderstandings,
uncertainty and ambiguity. The quality of the produced vocabularies is another
challenge that should be tackled as well. In [1], we identified and elaborated
important aspects for vocabulary development such as: reuse, vocabulary
structure, naming conventions, multilinguality, documentation, validation and
authoring. These aspects are relevant from collaborative point of view as
well. Taking into consideration above aspects will impact the quality of
vocabulary itself.

Therefore, finding a suitable collaboration methodology is exacerbated by the
number and diversity of the involved stakeholders as well as the complexity of
the domains. Due to the open, distributed and participatory nature of the Web,
such a solution is of paramount interest for the Semantic Web community.

Our approach to tackle the mentioned problem is to focus on supporting the
collaborative vocabulary development with a well-known method for distributed
version control in a domain-agnostic way. In this regard, we have chosen _Git_
for the following two reasons. On the one hand, Git is a mature version
control system supported by sophisticated tools and broadly used in software
development projects. More than 10 million
repositories222https://github.com/blog/1724-10-million-repositories are hosted
on GitHub for open source and commercial projects [2]. On the other hand,
existing popular vocabularies like _schema.org_
333{https://github.com/schemaorg/schemaorg}, _Description of a Project_
(DOAP)444{https://github.com/edumbill/doap}, the _music ontology_
555{https://github.com/motools/musicontology} publish their efforts in GitHub
to leverage the contribution of the community. This indicates that the
vocabulary development community is already familiar with Git.

The remainder of this paper is structured as follows: In section II we present
a comprehensive list of requirements aggregated from the current state of the
art and our ongoing work on _MobiVoc_ 666{https://github.com/vocol/mobivoc}
and _SCORVoc_ 777{http://purl.org/eis/vocab/scor}. In section III we present
_Git4Voc_ which comprises guidelines how Git can be used for collaborative
vocabulary development. With Git4Voc we propose to utilize Git’s hooks
mechanism to realize vocabular-specific features. In section IV we demonstrate
concrete example of hook implementations. We provide an overview about related
work in section V. The conclusion and an outlook to future work are presented
in section VI.

##  II Requirements of Collaborative Vocabulary Development

Collaborative vocabulary development is considered to be very related to the
broad field of software development. In fact, most proposals for supporting
the former are inspired by experiences in the latter. However, a vocabulary is
not totally equal to software code. The development of vocabularies raises
challenges which are new and not or at least not to that extend raised during
software development. In this section we focus on requirements which are more
critical for vocabularies. We gathered these requirements by aggregating
insights from the current state of the art and our own experiences during the
development of MobiVoc888{https://github.com/vocol/mobivoc} and
SCORVoc999{http://purl.org/eis/vocab/scor}. In the following these
requirements are presented in detail.

Communication support (R1) Collaborative vocabulary development is about
finding consensus between members of a team. In order to share ideas and
finding agreements, communication among the contributors is essential [3].
During the whole life cycle, especially in agile development, supporting and
recording discussions, changes and their reasons are crucial [4]. This is
especially very important in the case of heterogeneous teams with experts from
different domains. Some critical examples to be communicated within a team are
introducing new elements, extending or modifying the subsumption hierarchy,
integration of external resources and changing the underlying semantic
expressivity [5]. An effective communication has a significant impact on the
quality of the collaboration and its outcome.

Provenance of information (R2) In collaborative development the capability to
track the changes made by contributors is an important feature [4]. This is
due to the fact that each change in the vocabulary reflects the understanding
of the authors regarding the domain. In case of disagreements, it is necessary
to know which change was made by whom at which time and for what reason.

Different roles (R3) Creating vocabularies with the purpose of realizing data
integration across heterogeneous independent systems, involves domain experts
from various fields with different levels of expertise. For instance, in large
projects like the _Gene Ontology_ 101010{http://www.geneontology.org/} (GO)
many participants and curators take part in the development process. Most
participants can only add comments and discuss terms. A core team is allowed
to edit the main components of the vocabulary by adding modules, classes,
properties, removing terms and performing refactoring. For that reason, there
is a need for the definition of roles along with the permissions [5, 4, 6, 7].

Workflow independence (R4) The overall field of methodologies and workflows
for collaborative vocabulary development is changing continuously [4]. To the
best of our knowledge, there are no established methodologies nor workflows
which are broadly applied. Tools supporting collaboration should be generic
and be able to adapt in highly dynamic context. Therefore, it is important
that a system is flexible enough to be used within different methodologies and
workflows.

Quality assurance (R5) Developing vocabularies includes many requirements of
quality assurance. Syntax and semantic correctness as well as the application
of best practices on designing vocabularies are some of the quality aspects.
Therefore providing tool support is a significant feature to prevent
contributors from making errors. Later correcting phases might lead to a
wasting of resources in terms of time and money.

Documentation generation (R6) As mentioned before, a team for vocabulary
development comprises domain experts with less technical expertise in
knowledge representation and engineering tools. In order to enable them
contributing to the development process, providing user friendly view to the
current state of the vocabulary is vital. Therefore, an automatic
documentation generation feature is necessary.

Deltas among versions (R7) Collaborative development of vocabularies should
respond to the evolution of the knowledge domain [7]. It should also respect
the evolution of connected vocabularies within the Linked Data Cloud, in order
to avoid semantic inconsistencies. Therefore, support for detecting and
documenting the semantic difference between versions is needed, to enable
developers to understand the mentioned evolutions. This includes the
modification, the addition of new elements (i.e. classes, properties) as well
as the removal of existing terms. Authors of well-known vocabularies such as
_SKOS_ 111111{http://www.w3.org/2004/02/skos/history} and _schema.org_
121212{http://schema.org/docs/releases.html} publish release notes containing
what has been changed among different versions.

Editor agnostic (R8) In contrast to software code, vocabularies are abstract
artefacts which can be serialized with different techniques. Since
contributors can use different editors which style the syntax in different
ways, the support of the collaboration must be editor agnostic and syntax
independent.

Modularity (R9) Modularization is recognized as an important step in
collaborative vocabulary building [8]. Reusability, the decrease of
complexity, ownership and customization are some of the benefits of vocabulary
modularization. Some studies report that there is no universal way to perform
this process and that the choice of a particular technique should be guided by
application specific requirements [9]. In contrast, other reports show that a
module in a mid-sized vocabulary should contain between 200 and 300 lines of
code [10]. Especially in an agile development process with large vocabularies
and many contributors, it is of paramount importance that the system provides
means to support the modularization activity.

Multilinguality (R10) In order to have a wide range of applicability to
different cultures and communities, vocabulary terms must be translated into
various languages [11]. The localization (and internationalization) process of
vocabularies should be supported by the system.

Labeling versions (R11) Release versions of vocabularies should be labeled
appropriately. This ensures that users that can be humans or machines have
always the possibility to use specific version, not only the latest one.

##  III Git4Voc

In this section we present Git4Voc. On the one hand, we propose guidelines how
Git can be used for collaborative vocabulary development project. On the other
hand, we present how the requirements from section II can be technically
implemented by Git _hooks_. Additionally, in terms of guidelines we analyzed
best practices from collaborative software development and identified the
following aspects as critical for the quality of the vocabulary: (1)
management of generated information; (2) rights management; (3) branching and
merging; (4) automate development and deployment tasks by hooks; (5) tool
independence; (6) vocabulary organization structure; and (7) labeling of
release versions. In the next subsections we show in detail how our approach
responds to the above mentioned requirements.

###  III-A Management of Generated Information

During the development process a bunch of information is generated by the
contributors. The capability to manage this information within the entire
project life-cycle is essential. In fact, value added services like GitHub,
GitLab or BitBucket enrich Git functionality with powerful information
management features. For instance, issues are a great way of tracking
communications, reporting problems as well as bug fixes and announcing version
releases. Communities like _schema.org_ manage their discussions using GitHub.
The above mentioned means support requirement (R1). Based on this fact, we
propose that activities gathered in Table I should be documented. If possible,
the name of issues should correspond to the name of the activities.

Another important requirement in collaborative vocabulary development is the
ability to view the history of the changes (called traceability in software
engineering). This addresses the requirement (R2). Using commands _git log_
and git diff a user can explore the history of the commits and the differences
between them. Each commit should be realized based on _Best Commit Practices
131313{http://www.git-tower.com/learn/git/ebook/command-line/appendix/best-
practices}_. In vocabulary development the _atomicity_ of commits is of
paramount importance.

###  III-B Rights Management

Standalone solutions such as _GitLab_ 141414{https://gitlab.com/gitlab-
org/gitlab-ce/blob/master/doc/permissions/permissions.md} and _Gitolite_
151515{https://github.com/sitaramc/gitolite} as well as third-party services
like _Bitbucket_
161616{https://confluence.atlassian.com/display/BITBUCKET/Add+Users,+Set+Permissions,+and+Review+Account+Plans}
and _GitHub_ 171717{https://help.github.com/articles/permission-levels-for-an-
organization-repository} offer basic options for user rights managements, like
reading, writing, posting, adding new team members and adding tags. However,
even with these solutions a high level of user management i.e. restricting
editing a specified number or type of classes, properties or instances cannot
be achieved with Git. In order to address requirement (R3), we explore a
combination of branching and hooks.

[ label=tab:roles, pos = tb, caption=Different roles and their primary
activities., ]lcccRoles & Basic Semantic Structural
Activities Issues Issues Vocabulary Eng. + + + Domain Expert + - - Users - - -
Translators + - -

With the combination of branching and hooks with role definition for users,
fine grained access management can be achieved. Concretely, by using server-
side hooks, realizing rights managements on top of user roles is possible. For
instance, an implementation of a _pre-push_ hook can check for the user’s role
and permissions and deny if the necessary rights according the activity and
branch are not set.

LABEL:tab:roles shows common roles and their permissions, with respect to the
defined categories of activities. In a trusted environment right management
can also be realized with client-side hooks. An example for this is depicted
in 3, where the user is denied to push to the master branch.

###  III-C Branching and Merging

TABLE I: Common Activities in Collaborative Vocabulary Engineering Activity |  Name |  Description |  Example
---|---|---|---
ACT1 |  Simple Addition/Deletion |  Adding new or deleting existing elements like classes and properties |  Adding a class in the last level of the taxonomy
ACT2 |  Complex Addition/Deletion |  Adding new elements to be interconnected within the existing class or properties taxonomy |  Adding a object property as a super property of two existing properties
ACT3 |  Modification |  Modifying existing elements |  Modifying the domain and range of an existing object property
ACT4 |  Reusing |  Reusing elements of the Linked Data Cloud |  Defining new local concepts by using external resources
ACT5 |  Alignment |  Alignment of existing elements with equivalents in the cloud |  Alignment of classes and instances with _owl:equivalentClass_ and _owl:sameAs_
ACT6 |  Refactoring |  Changing the name and metadata of an specific element and its connections |  Renaming a class which is connected in many domain and range relation of properties and need to be renamed everywhere
ACT7 |  Common Metadata |  Adding/Removing/Modifying predefine _RDFS_ metadata |  Adding metadata to a class with _rdfs:label, rdfs:comment_
ACT8 |  External Metadata |  Adding/Removing/Modifying external metadata |  Adding metadata to a class with _skos:prefLabel, dc:title_
ACT9 |  Translating |  Adding/Removing/Modifying translation for the terms |  Using _rdfs:label_ to translate elements into different languages
ACT10 |  Modularization |  Adding new modules to the existing vocabulary |  Creating and integrating new modules due to new requirements
ACT11 |  Partitioning |  Partitioning into different modules with existing elements |  The vocabulary has grown in size and semantic complexity. Partitioning the existing vocabulary into different modules

Git is a very flexible tool, which addresses requirement (R4). Using Git,
teams are able to organize their work in different types of
workflows181818{https://www.atlassian.com/git/tutorials/comparing-
workflows/forking-workflow}. Branching strategies affect the quality in
collaborative software development [12, 13]. Vocabulary development is mostly
accepted to be a specific type of software development. Therefore, it is
considered that the branching strategy affects the quality of the
vocabularies. Well-known projects such as _schema.org_ use branches to
organize their work. In order to design a branching model, it is important to
understand the possible activities that a team can perform. In this regard, we
collected common activities of collaborative vocabulary development which are
listed in Table I. Aiming at producing a vocabulary with good quality, the
entire team should be aware of these activities and how to face them in the
development process. Due to their impact on the overall vocabulary, we have
classified these activities into three categories: (1) basic activities
(_ACT1, ACT7, ACT9_), (2) semantic issues (_ACT2, ACT3, ACT4, ACT5, ACT6,
ACT8_) and (3) structural issues (_ACT10, ACT11_).

This led us to the branching model that is depicted in Figure 1. We designed
different branches to handle the mentioned categories. Basic activities have
to be performed in the Develop Branch. For the second category we propose a
dedicated branch called Semantic Issues. In case of the third category a
branch named Structural Issues has to be applied. It is important to bear in
mind that we are not restricting the flexibility of Git regarding branches. On
the contrary, other branches can be used as a complement of this model.
Nevertheless, our approach of branching model will help developers because
those branches are connected to specific activities in collaborative
vocabulary development.

Our solution is built on top of the best practices for branching in software
development191919{http://nvie.com/posts/a-successful-git-branching-model}.

Figure 1: Branching model for vocabulary development

###  III-D Automate Development and Deployment Tasks by Hooks

Despite the fact that Git has many implemented features, it allows extending
its functionality by using so-called hooks. This is a mechanism that allows
running scripts before or after specific Git events. Based on the execution
place, two types of hooks are distinguished, client-side and server-side
hooks. Due to space limitations, the examples in this article showcase only
client-side hooks. In order to address requirements (R5) and (R6), we
implemented the following three important tasks for collaborative vocabulary
development: (1) syntax checking, (2) assessing vocabularies against best
design practices and (3) documentation generation. Figure 2 illustrates how
these examples are integrated into the _commit_ process.

After modifying the local vocabulary and adding changes to the stage phase,
the next step is to _commit_ the current state to the local repository. The
initialization of commit triggers a hook named pre-commit. 3 shows our
implementation of this hook which realizes the tasks syntax checking and best
practice assessment. First, it retrieves all modified files with extensions
such as rdf, owl, ttl and checks for syntax errors by using
Rapper202020{http://librdf.org/raptor/}. In case that vocabularies fail to
pass the validation process, the commit is canceled. The user is notified with
a message which shows detailed description about the error which comprised of
the file name, line number and the error type. If syntax validation is passed
successfully, the modified files are posted to the _OOPS_ 212121{http://oops-
ws.oeg-upm.net/} Web Service through curl, a command-line HTTP client. This
service assesses vocabulary files for certain quality metrics. The result of
this is a descriptive message that contains recommendations of best practices
for vocabulary development. If no errors exist, the pre-commit hook is
finished and the commit is accepted. Afterwards a post-commit hook is called.
4 demonstrates our implementation of a post-commit hook for documentation
generation in a human friendly format. This script uses _Parrot_
222222{https://bitbucket.org/fundacionctic/parrot/} as an external tool.

Figure 2: Client-side Hooks Workflow

For security reasons Git repository services do not allow to automatically
distribute predefined hooks on cloning phase. In order to accomplish this
task, the repository itself should have a dedicated folder that contains the
implemented hooks. After the first clone, these hooks need to be copied to the
.git/hooks directory. For that purpose, we implemented a script which needs to
be executed after cloning the repository. Once this process is finished,
predefined hooks will be automatically executed after each commit. However,
when the hooks have been changed, e.g. to use different validation or
documentation generation tools, this script has to be executed again. Apart
from installing the hooks, this script can also be used to download and
install tools like Rapper, which are necessary for the hooks. If these tools
are to be placed within the local repository, the file .gitignore should be
used to prevent them from being pushed to the remote repository.

Git does not show semantic diffs between versions of vocabulary. Owl2VCS [14]
shows deltas among different versions. By using such a tool and hooks,
generated deltas can be published is human friendly format as well. This
corresponds to the requirement (R7).

###  III-E Tool Independence

Collaborative working with Git can be facilitated by using vocabulary editors
like _Protégé_ 232323{http://protege.stanford.edu/}, _TopBraid Composer_
242424{http://www.topquadrant.com/tools/IDE-topbraid-composer-maestro-
edition/}, _Neon Toolkit_ 252525{http://neon-toolkit.org/wiki/Main_Page.html}.
As each of them has different algorithms for writing files, there might arise
consistency problems in case that contributors are not using the same editor.
For instance, one contributor use Protégé, whereas another one uses Neon
Toolkit. They are editing the same file simultaneously. After saving it,
different representations of that file will be created. As a consequence Git
recognizes lot of changes and asks for conflict resolution. This is due to
fact that Git is a version control based on text line changing. It detects
when a line has been changed from the previous version. In such a case using
the merge tool is necessary, which is a time consuming and error prone task
that could lead to information lose.

In order to avoid the above mentioned problems, we propose the use of Turtle
format. This addresses the requirement (R8). A similar approach describes a
pattern to express data on GitHub storing it in CSV
files262626{http://blog.okfn.org/2013/07/02/git-and-github-for-data/}. 1
presents our proposal to write one triple per line.

Listing 1: One triple per line

⬇

@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>.

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#>.

@prefix owl: <http://www.w3.org/2002/07/owl#>.

@prefix scor: <http://purl.org/eis/vocab/scor#>.

@prefix vs: <http://www.w3.org/2003/06/sw-vocab-status/ns#>.

scor:Process

rdf:type owl:Class ;

rdfs:comment "A process is a unique activity..."@en ;

rdfs:label "Process"@en ;

rdfs:isDefinedBy scor: ;

vs:term_status "testing".

scor:Enable

rdfs:subClassOf scor:Process ;

rdfs:comment "Enable describes the ...";

rdfs:label "Enable".

###  III-F Vocabulary Organization Structure

Git’s basic functionalities do not support modularizing code or vocabularies.
Therefore, in order to address the requirement (R9), we propose some
guidelines for organizing the vocabulary in files where each file represents a
module. Considering the fact that each line should represent a triple and
based on the insights on [10], we propose that files should not contain more
than 300 triples. We highlight three possible forms of organizing the files.
All of these cases use single Git repository to store the files.

_1\. The complete vocabulary is contained in one single file._ When the
vocabulary is small (e.g. contains less than 300 lines of code) and represents
a domain which cannot be divided in sub domains, it should be saved within one
single file. If the number of contributors is relatively small and the domain
of the vocabulary is very focused, organizing it into one single file might be
possible, even if it exceeds 300 lines of code. However, if the
comprehensibility is exacerbated, splitting it into different files should be
considered.

_2\. The vocabulary is split in multiple files._ If the vocabulary contains
more than 300 lines of code or covers a complex domain, it should be organized
into different sub domains or modules. In this regard, we mapped sub domains
with modules. When the sub domains themselves are small enough they should be
represented by different files within the parent folder. There exists patterns
for vocabulary modularization [15]. We developed the MobiVoc based on the
pattern n modules importing 1 module. In this case, 1 module was the
vocabulary itself. The n modules like Aircraft, Fuel were saved in separate
files. Each file represents a specific sub domain. By following this approach,
domain experts can contribute independently to vocabulary development
according to their field of expertise. Figure 3 depicts the structure of
MobiVoc and its modules.

Figure 3: The structure of MobiVoc

_3\. Vocabulary modules are stored in files and folders._ For huge
vocabularies that comprises complex domains, splitting it into files is not
sufficient. This would lead to a large amount of files within a single folder.
Therefore, if the sub domains are large enough to be split into files they
should be represented by folders. Each folder contains files which represents
modules. In this case, the folder and file structure should reflect the
complex hierarchy of the overall domain.

Through splitting the vocabulary in files for specific purposes, the
requirement (R10) is addressed as well. This can be achieved by creating
dedicated files for translating. In these files users with the role
Translators can contribute by translating the terms into the required
language.

###  III-G Labeling of Release Versions

Based on requirement (R11), proper labeling of release versions is vital, as
it facilitates re-usability. One of the common ways to realize that is to
deploy each release version in different files. However, this could lead to
following problems as identified in [16]: (1) the number of files could
increase rapidly, (2) choosing versions creates confusion, (3) maintenance
needs additional resources and (4) synchronizing with latest version from
dependent applications requires additional effort. To avoid the above
mentioned problems, we have kept versions of vocabularies in the same file.
These versions are separated by Git implemented functionality of tagging and
saved in the master branch which is part of the branching model and
illustrated in Figure 1. It is possible to create and filter tags at any time.
Moreover, users can obtain a specific version of the vocabulary just by giving
the tag name. Therefore, each released version of a vocabulary _must_ have a
version number. Based on the scheme from [17] and the mentioned categories of
activities in Table I, we propose tagging different versions according to the
following pattern: _v[StI.SeI.BA]_ , where _StI_ stands for Structural Issues,
_SeI_ for Semantic Issues and _BaA_ for Basic Activities. Each category is
related with a number, in the respective position. Changes in the vocabulary
regarding to the categories are commonly reflected by increasing the numbers.
For instance, the difference between releases _v[1.0.0]_ and _v[2.0.0]_ shows
structural issue changes (_StI_).

##  IV Implementation

We have developed
Git4Voc272727https://github.com/vocol/vocol/tree/master/Git4Voc, which is an
environment for collaborative vocabulary development. Table II provides an
overview which of the previously described requirements are fulfilled by
Git4Voc. This solution combines Git4Voc with a set of state-of-the-art tools
like Rapper, OOPS Service and Parrot. Each tool is exchangeable and can be
easily replaced by alternatives. They provide services which are called by the
hooks mechanism. In the following these hooks are presented in detail.

TABLE II: Collaborative Requirements from Git4Voc perspective. No. |  Requirement |  Supported |  Means
---|---|---|---
|  |  by plain Git |
R1 |  Communication support |  + |  Issues tracking system offered by hosting platforms GitHub, GitLab, BitBucket
R2 |  Provenance of information |  + |  Git log and git diff functionality
R3 |  Different roles |  + |  Further extension by a combination of branching and hooks
R4 |  Workflow independence |  + |  Git, branching and merging strategies
R5 |  Quality assurance |  - |  Extended by a combination of hooks and tools like: Rapper, JenaRiot
R6 |  Documentation generation |  - |  Extended by a combination of hooks, documentation generation tools like: SchemaOrg, Widoco
R7 |  Deltas among releases |  - |  Extended by a combination of Owl2VCS as an external tool and hooks
R8 |  Editor agnostic |  + |  Git base functionality
R9 |  Modularity |  + |  Hierarchy organization of vocabularies where modules are represented by files
R10 |  Multilinguality |  + |  Hierarchy organization of vocabularies where dedicated files are used for multilinguality
R11 |  Labeling versions |  + |  Git tag functionality

The 2 shows an example how predefined hooks are copied into the .git/hooks
folder after cloning the repository. In addition, it shows installing of the
tools: Raptor and Parrot and their necessary libraries in case they do not
exist.

Listing 2: Install Hooks and Tools

⬇

#!/bin/sh

# Copy the modified hooks

for i in ‘ls -1 hooks‘ do

cp hooks/$i .git/hooks/$i

done

# Create directory for necessary tools

if [ -d "$tools" ]; then

mkdir -p "tools"

...

fi

cd tools

#Install Raptor

if [ ! -d "$Raptor" ]; then

curl -O http://download.librdf.org/source/raptor2-2.0.15.tar.gz

...

sudo apt-get install libxml2-dev libxslt1-dev python-dev

sudo apt-get -y install raptor2-utils

...

fi

#Install Parrot

if [ ! -e "parrot-jar-with-dependencies.jar" ]; then

curl -O https://github.com/vocol/vocol/raw/master/Hooks/tools/parrot-jar-with-
dependencies.jar

fi

...

The pre-commit hook is adapted to prevent users from committing to the master
branch as shown in the 3. This example can be further customized to restrict
committing to other branches as well. By doing so, a low level of rights
management is achieved on the local repository, before the changes are pushed
to the remote repository. Furthermore, to reduce the efforts needed for
subsequent corrections, we integrated tools for (1) syntax validation; and (2)
checking for bad modeling practices. For the first, the Rapper tool is used,
which validates each turtle file for syntactic errors. For the second, we used
OOPS Web Service to scan vocabulary files for bad modeling practices.

Listing 3: Pre-Commit Hook: Syntax validation and checking for bad modeling
practices

⬇

#!/bin/bash

currentBranch=$(git symbolic-ref HEAD)

if [ "$currentBranch" = "refs/heads/master" ]; then

echo "Not allowed to commit to master branch!"

exit 1

else

# Get only modified files with ttl extension

files=$(git diff \--cached \--name-only \--diff-filter=ACM | grep ".ttl$")

...

for file in ${files}; do

# Validate each file using Rapper

res=$(rapper -i turtle "${files}" -c 2>&1)

...

if ! $error; then

for file in ${files}; do

fileContent=‘cat ${files}‘

request="<?xml ...>"

res=$(curl -X POST -d "$request" -H "Content-Type: application/xml"
http://oops-ws.oeg-upm.net/rest)

...

done

fi

if ${succeed}; then

echo "COMMIT SUCCEEDED"

else

echo "COMMIT FAILED"

exit 1

fi

fi

The 4 shows the post-commit hook, which uses Parrot to create the human
friendly representation of the developed vocabulary. The generated content is
saved as a single HTML file which consists of all vocabulary elements. User is
able to navigate through entire vocabulary by merely selecting the element
name. Moreover, in order to create different representation style of the
vocabulary, alternative tools such as: _Widoco_
282828{https://github.com/dgarijo/Widoco}, _Specgen_
292929{https://github.com/specgen/specgen}, _Dowl_
303030{https://github.com/ldodds/dowl}, etc. (c.f. commented part of the code)
can be used as well.

Listing 4: Post-Commit Hook: Documentation Generation

⬇

#!/bin/sh

files=$(git diff \--cached \--name-only \--diff-filter=ACM | grep ".ttl$")

if [ "$files" = "" ]; then

exit 0

fi

for file in ${files}; do

# Generate documentation using Parrot

java -jar @path/parrot-jar-with-dependencies.jar -i "${file}" -o
"${file}".html

# Generate documentation using Widoco

# java -jar @path/widoco-0.0.1-jar-with-dependencies.jar -ontFile "${file}"
-outFolder /home/

...

done

echo "\Documentation Generation is completed.\n"

exit 1

##  V Related Work

Collaborative vocabulary development is an active research area in the
Semantic Web community [19]. Existing approaches like _WebProtégé_ [20]
provides a collaborative web frontend for a subset of the functionality of the
Protégé OWL editor. The aim of WebProtégé, is to lower the threshold for
collaborative ontology development. _Neologism_ [21] is a vocabulary
publishing platform, with a focus on ease of use and compatibility with Linked
Data principles. Neologism focuses more on vocabulary publishing and less on
collaboration. VocBench [22], is an open source web application for editing
thesauri complying with the SKOS and SKOS-XL standards. VocBench has a focus
on collaboration, supported by workflow management for content validation and
publication.

The main limitation of the aforementioned tools is the lack of version
control. Therefore, we only consider approaches focused on using version
control systems for collaborative vocabulary development.

_SVoNt_ [23] extends the functionality of Apache SubVersion (SVN) by providing
a possibility for versioning OWL conform lightweight description logic. SVN
manipulates only with deltas of files, therefore SVoNt use a separate server
to create conceptual changes between versions of ontologies. These changes are
generated as a result of diff operation between the modified ontology and the
base ontology. _ContentCVS_ [24] is a Protégé plugin. It adapts concepts from
_concurrent versioning_ to enable developers to work in parallel. Moreover, it
has features for conflict detection and resolution by checking structure and
semantic of the ontology versions. In [17] is described how the developers of
_RDA Vocabularies_ 313131{http://www.rdaregistry.info} adopt rules from
_SemVer_ 323232{http://www.semver.org} to realize a meaningful versioning
using Git. Additionally, it provides general notes for organizing the
vocabulary development in branches. [25] describes Owl2VCS, a toolset designed
to facilitate version control of OWL 2 ontologies using version control
systems. It can be integrated as an external tool with Git, Mercurial and
Subversion and provide algorithms for structural diff [14]. However, none of
the above mentioned approaches cover all the identified requirements (c.f.
section II) for collaborative vocabulary development. On the contrary, our
work analyze and address each one of them by using Git and Git4Voc as an
extension.

##  VI Conclusion and Future Work

In this paper, we investigated the applicability of Git for collaborative
vocabulary development. We defined collaborative vocabulary development as the
process of identifying the main terms across heterogeneous data sources by
finding a consensus between the developers. The main challenge in this regard
is the realization of a powerful collaborative environment. Distributed
version control systems enable developers around the world to work
collaboratively on complex software systems. Since software and vocabularies
are not the same, we analyzed their differences in detail by identifying
requirements for a version control system that supports collaborative
vocabulary development. Our approach extends plain Git functionality by
utilizing the hooks mechanism in combination with external tools to address
these requirements. The presented approach is easily extensible and can
accommodate additional external tools.

Regarding the future work, we are going to extend our approach with the full
implementation of server side hooks. By doing so, tasks like: deploying
specific versions of vocabularies to a dedicated server, generating
deferencable URI’s, ontology partitioning and modularization tasks can be
performed in a fully automated way. We also plan to develop and integrate a
tool that validates vocabularies against conventions [1] and provides
recommendations for solving possible issues. This will lead to a convenience
and less error prone collaborative vocabulary development environment. As a
result, all generated artefacts will be publicly accessible from all
interested parts.

## Acknowledgments

This work is supported by the German Ministry for Education and Research
funded project LUCID and European Commission under the Seventh Framework
Program FP7 for grant 601043 (http://diachron-fp7.eu).

## References

  * [1] I. Grangel-González, L. Halilaj, G. Coskun and S. Auer, “Towards vocabulary development by convention,” in _7th International Joint Conference on Knowledge Discovery, Knowledge Engineering and Knowledge Management, Vol 2_ , 2015, pp. 334–343.
  * [2] E. Kalliamvakou, D. Damian, K. Blincoe, L. Singer, and D. German, “Open source-style collaborative development practices in commercial projects using github,” in _37th International Conference on Software Engineering (ICSE’15)_ , 2015.
  * [3] N. F. Noy, A. Chugh, W. Liu, and M. A. Musen, “A framework for ontology evolution in collaborative environments,” in _ISWC_. Springer, 2006, pp. 544–558.
  * [4] N. F. Noy and T. Tudorache, “Collaborative ontology development on the (semantic) web.” in _AAAI Spring Symposium: Symbiotic Relationships between Semantic Web and Knowledge Engineering_ , 2008, pp. 63–68.
  * [5] J. Seidenberg and A. L. Rector, “The state of multi-user ontology engineering.” in _WoMO_. Citeseer, 2007.
  * [6] T. Tudorache, N. F. Noy, S. M. Falconer, and M. A. Musen, “A knowledge base driven user interface for collaborative ontology development,” in _16th International Conference on Intelligent User Interfaces_. ACM, 2011, pp. 411–414.
  * [7] E. Simperl and M. Luczak-Rösch, “Collaborative ontology engineering: a survey,” _The Knowledge Engineering Review_ , vol. 29, no. 01, pp. 101–131, 2014.
  * [8] M. C. Suarez-Figueroa, A. Gómez-Pérez, and M. Fernandez-Lopez, “The neon methodology for ontology engineering,” in _Ontology engineering in a networked world_. Springer, 2012, pp. 9–34.
  * [9] M. d’Aquin, A. Schlicht, H. Stuckenschmidt, and M. Sabou, “Ontology modularization for knowledge selection: Experiments and evaluations,” in _Database and Expert Systems Applications_. Springer, 2007, pp. 874–883.
  * [10] A. Schlicht and H. Stuckenschmidt, “Towards structural criteria for ontology modularization,” in _ISWC 2006 Workshop on Modular Ontologies_. Citeseer, 2006.
  * [11] J. Gracia, E. Montiel-Ponsoda, P. Cimiano, A. Gómez-Pérez, P. Buitelaar, and J. McCrae, “Challenges for the multilingual web of data,” _Journal of Web Semantics_ , vol. 11, pp. 63–71, 2012.
  * [12] S. Phillips, J. Sillito, and R. Walker, “Branching and merging: an investigation into current version control practices,” in _4th International Workshop on Cooperative and Human Aspects of Software Engineering_. ACM, 2011, pp. 9–15.
  * [13] E. Shihab, C. Bird, and T. Zimmermann, “The effect of branching strategies on software quality,” in _ACM-IEEE International Symposium on Empirical Software Engineering and Measurement (ESEM)_. IEEE, 2012, pp. 301–310.
  * [14] R. S. Gonçalves, B. Parsia, and U. Sattler, “Ecco: A hybrid diff tool for owl 2 ontologies.” in _OWLED_ , 2012.
  * [15] S. B. Abbes, A. Scheuermann, T. Meilender, and M. d’Aquin, “Characterizing modular ontologies,” in _7th International Conference on Formal Ontologies in Information Systems (FOIS)_ , 2012, pp. 13–25.
  * [16] P. Bedi and S. Marwaha, “Versioning owl ontologies using temporal tags,” _International Journal of Computer, Control, Quantum and Information Engineering_ , 2007.
  * [17] J. P. Diane I. Hillmann, Gordon Dunsire, “Versioning vocabularies in a linked data world,” _IFLA Lion_ , 2014.
  * [18] _VoCol: An Agile Methodology and Environment for Collaborative Vocabulary Development_. Zenodo, Feb. 2015. [Online]. Available: http://dx.doi.org/10.5281/zenodo.15023
  * [19] R. Palma, O. Corcho, A. Gómez-Pérez, and P. Haase, “A holistic approach to collaborative ontology development based on change management,” _Journal of Web Semantics_ , vol. 9, no. 3, pp. 299–314, 2011.
  * [20] T. Tudorache, C. Nyulas, N. F. Noy, and M. A. Musen, “Webprotégé: A collaborative ontology editor and knowledge acquisition tool for the web,” _Semantic Web_ , vol. 4, no. 1, 2013.
  * [21] C. Basca, S. Corlosquet, R. Cyganiak, S. Fernández, and T. Schandl, “Neologism: Easy vocabulary publishing,” 2008.
  * [22] A. Stellato, S. Rajbhandari, A. Turbati, M. Fiorelli, C. Caracciolo, T. Lorenzetti, J. Keizer, and M. T. Pazienza, “Vocbench: A web application for collaborative development of multilingual thesauri,” in _The Semantic Web. Latest Advances and New Domains_. Springer, 2015, pp. 38–53.
  * [23] M. Luczak-Rösch, G. Coskun, A. Paschke, M. Rothe, and R. Tolksdorf, “Svont-version control of owl ontologies on the concept level.” _GI Jahrestagung (2)_ , vol. 176, pp. 79–84, 2010.
  * [24] E. Jiménez-Ruiz, B. C. Grau, I. Horrocks, and R. B. Llavori, “Contentcvs: A cvs-based collaborative ontology engineering tool.” in _SWAT4LS_. Citeseer, 2009.
  * [25] I. Zaikin and A. Tuzovsky, “Owl2vcs: Tools for distributed ontology development.” in _OWLED_. Citeseer, 2013.


* [18] M. Hairer, J.C. Mattingly, Ergodicity of the 2D Navier–Stokes equations with degenerate stochastic forcing. Ann. of Math. (2006)(2) 164 993–1032.
  * [19] N. Ikeda, S. Watanabe, Stochastic Differential Equations and Diffusion Processes, 2nd ed. North-Holland Mathematical Library 24. North-Holland, Amsterdam (1989).
  * [20] V. Jaksic, V. Nersesyan, C.-A. Pillet, A. Shirikyan, Large deviations from a stationary measure for a class of dissipative PDEs with random kicks. Comm. Pure Appl. Math. 68 (2015), no. 12, 2108-2143.
  * [21] V. Jaksic, V. Nersesyan, C.-A. Pillet, A. Shirikyan, Large deviations and mixing for dissipative PDEs with unbounded random kicks. Nonlinearity, 31(2):540-596, 2018
  * [22] V. Jaksic, V. Nersesyan, C.-A. Pillet, A. Shirikyan, Large deviations and entropy production in viscous fluid flows. Arch. Ration. Mech. Anal, 240:1675–1725, 2021
  * [23] R. Kapica, T. Śzarek, M. Sleczka, On a unique ergodicity of some Markov processes. Potential Analysis, 2012, 36 (4) 589-606.
  * [24] T. Komorowski, S. Peszat, T. Szarek, On ergodicity of some Markov processes. Ann. Probab. 38 (2010), no. 4, 1401-1443.
  * [25] D. Martirosyan and V. Nersesyan, Local large deviations principle for occupation measures of the stochastic damped nonlinear wave equation. Ann. Inst. Henri Poincare Probab. Stat., 54(4):2002-2041, 2018.
  * [26] V. Nersesyan, X. Peng, L. Xu, Large deviations principle via Malliavin calculus for the Navier-Stokes system driven by a degenerate white-in-time noise, arXiv:2201.12977
  * [27] S. Peszat, J. Zabczyk, Strong Feller property and irreducibility for diffusions on Hilbert spaces. Ann. Probab. 1995, 157-172.
  * [28] S. Peszat, J. Zabczyk, Stochastic Partial Differential Equations with Lévy Noise: Evolution Equations Approach, Cambridge University Press, Cambridge, 2007
  * [29] E. Priola, J. Zabczyk, Structural properties of semilinear SPDEs driven by cylindrical stable process, Probab. Theory Relat. Fields 149 (2011), 97-137.
  * [30] J. Rosinski, Tempering stable processes, Stoch. Process. Appl. 117 (6) (2007) 677-707.
  * [31] K. Sato, Lévy Processes and Infinitely Divisible Distributions. Cambridge University Press, 1999.
  * [32] R. Temam, Local Existence of $C^{\infty}$ Solutions of the Euler Equations of Incompressible Perfect Fluids, in: Lecture Notes in Math., vol. 565, 1976, pp. 184–194.
  * [33] L. Tolomeo, Unique ergodicity for a class of stochastic hyperbolic equations with additive space-time white noise. Comm. Math. Phys. 377 (2020), no. 2, 1311-1347.
  * [34] U. Küchler, S. Tappe, Tempered stable distributions and processes. Stochastic Process. Appl. 123 (2013), no. 12, 4256-4293.
  * [35] J. Wang, J. Zhai, J. Zhu, The stochastic nonlinear Schrödinger equations driven by pure jump noise, arXiv:2207.03719.
  * [36] R. Wang, J. Xiong, L. Xu, Irreducibility of stochastic real Ginzburg-Landau equation driven by $\alpha$-stable noises and applications. Bernoulli, 23 (2) (2017), 1179-1201.
  * [37] R. Wang, L. Xu, Asymptotics for stochastic reaction-diffusion equation driven by subordinate Brownian motion. Stochastic Process. Appl. 128 (5) 2018, 1772-1796.
  * [38] L. Wu, Large and moderate deviations and exponential convergence for stochastic damping Hamiltonian systems, Stochastic Process. Appl. 91 (2) (2001), 205-238.
  * [39] L. Xie, X. Zhang, Ergodicity of stochastic differential equations with jumps and singular coefficients. Ann. Inst. Henri Poincaré Probab. Stat., 56(1) 2020, 175-229.
  * [40] B. Zdzislaw, W. Liu, J. Zhu, Strong solutions for SPDE with locally monotone coefficients driven by Lévy noise. Nonlinear Anal. Real World Appl. (17) (2014): 283-310.
  * [41] X. Zhang, Exponential ergodicity of non-Lipschitz stochastic differential equations. Proc. Amer. Math. Soc. 137 (1) (2009), 329-337.


# Feature-Adaptive Interactive Thresholding of Large 3D Volumes

Thomas Lang  FORWISS, University of Passau & Fraunhofer Institute of
Integrated Circuits, Division Development Center X-ray Technology
<EMAIL_ADDRESS>and  Tomas Sauer  Chair of Digital Image
Processing; FORWISS, University of Passau & Fraunhofer Institute of Integrated
Circuits, Division Development Center X-ray Technology  tomas.sauer@uni-
passau.de

###### Abstract.

Thresholding is the most widely used segmentation method in volumetric image
processing, and its pointwise nature makes it attractive for the fast handling
of large three-dimensional samples. However, global thresholds often do not
properly extract components in the presence of artifacts, measurement noise or
grayscale value fluctuations. This paper introduces _Feature-Adaptive
Interactive Thresholding_ (FAITH), a thresholding technique that incorporates
(geometric) features, local processing and interactive user input to overcome
these limitations. Given a global threshold suitable for most regions, FAITH
uses interactively selected seed voxels to identify critical regions in which
that threshold will be adapted locally on the basis of features computed from
local environments around these voxels. The combination of domain expert
knowledge and a rigorous mathematical model thus enables a very flexible way
of local thresholding with intuitive user interaction. A qualitative analysis
shows that the proposed model is able to overcome limitations typically
occuring in plain thresholding while staying efficient enough to also allow
the segmentation of big volumes.

###### Key words and phrases:

Interactive and Image Segmentation and Geometry and Optimization

##  1\. Introduction

Volumetric segmentation is concerned with the partitioning of three-
dimensional images into disjoint regions with the goal to extract further
information about selected components. In particular in computed tomography or
similar imaging methods, segmentation was always a crucial part of many
applications, including clinical tomography, nondestructive inspection of
parts or industrial quality control.

Although the underlying idea appears very simple, volumetric segmentation is a
hard problem in practice, in particular in modern volume processing as the
increasing size of the images, i.e., the number of volume elements, or
_voxels_ , scales cubically with the resolution. With ever-increasing imaging
capabilities high resolution digital volumes that do not fit into main memory
anymore are generated on a regular basis. Therefore plain computational
complexity prohibits many approaches and enforces local processing. While
pointwise thresholding does so, its limitations prevent high quality
segmentation results.

Another problem stems from the concept of generality. Ideally, one would like
to have a single segmentation method which can do everything for any type of
image. Since this goal is unrealistic, many and foremost medical applications
developed specialized algorithms to extract objects of a very particular type
exclusively. In this line of work, a new algorithm has to be designed for
every object category that shall be segmented, which is impractical for
industrial purposes with their infinity of different applications.

In the sequel we will assume that volumes consist of voxels associated to each
3D position having a _nonnegative_ value. Our procedure will perform
computations on local environments extracted around individual voxels only.
Let us formalize that.

######  Definition 1.1.

A _volume_ $V$ of dimensions $\bm{d}\in\mathbb{N}^{3}$ consist of voxels
located on a regular grid having positions $\bm{\alpha}\leq\bm{d}$. To each
point in this grid, a voxel grayscale value $x_{\bm{\alpha}}\geq 0$ is
associated. The _local environment_ of size $K^{3}$ centered around the voxel
at position $\bm{\alpha}$ is defined as the set of voxels

$\left\\{\bm{\beta}\leq\bm{d}\mid\|\bm{\beta}-\bm{\alpha}\|_{\infty}\leq\lfloor
K/2\rfloor\right\\};$

for convenience, we assume that the environment size satisfies $K\in
2\mathbb{N}+1$.

The simplest and most widely used segmentation procedure is _(hard)
thresholding_ , a binarization based on a _global threshold_ $\theta\geq 0$
and defined as

(1) $T_{\theta}(x)=\begin{cases}1,&x\geq\theta,\\\
0,&\text{otherwise}.\end{cases}$

For surprisingly many applications this procedure is sufficient and it is
perfectly applicable for big volumes since only information about the
currently processed voxel is necessary for computing the result. However,
especially in industrial computed tomography artifacts and physical effects
frequently distort the grayscale values of certain parts of the object. In
such regions, global thresholding is typically not able to capture the desired
structure and thus produces “holes” there. An illustration of this effect is
provided in Figure 1(c) which shows such holes at the top of the eye sockets
of a skull. In those regions, a local binarizing threshold needs to be smaller
than the global one, but if the global threshold would be adapted to a lower
level, other parts of the volume would include mis-segmentations.

The paper is organized as follows. In Section 2, we briefly summarize existing
approaches to adaptive thresholding, Section 3 introduces our model as an
optimization problem and provides an algorithm for solving this problem and we
motivate why our method is well suited for segmenting big voxel volumes. In
Section 4 we apply our algorithm to selected datasets and demonstrate the
improvement over plain thresholding. Finally, Section 5 summarizes our
contributions.

##  2\. Related Work

Of course, local thresholding itself is no new idea, notable examples include
the techniques by Niblack [1] and Sauvola [2]. Both methods choose optimal
binarizing thresholds in certain regions based on the local grayscale value
distribution. However, in presence of high variance inside such regions, as it
is often the case with measurement noise in industrial computed tomography,
these methods compute a threshold which basically captures everything
regardless of any structure. [3] computes a local threshold by comparing voxel
values to the mean grayscale values in local regions and segments a voxel if
it close enough to the average, while [4] computes local thresholds in
overlapping regions using Rosin’s method, interpolates a high resolution
threshold map and performs the pointwise comparison. On the other hand, [5]
and [6] perform local thresholding by combining a global threshold with edge
detection and morphological image processing to change the thresholding
behavior locally. [7] computes a two-dimensional Dual Tree Complex Wavelet
Transform for each volume slice and chooses local thresholds depending on the
estimated noise level in order to reduce measurement noise. The work in [8]
combines iterative image partitioning based on thresholds with local threshold
estimation. Here, after one step of partitioning, a new local threshold is
chosen from the grayscale value distribution for each partition based on which
a new finer partitioning is found. An interesting yet computationally
expensive approach was presented in [9]. There, the authors consider the
thresholding process as a pixelwise functional which, after solving the
according variational minimization problem, segments the image.

These approaches choose a threshold for each individual voxel. On the other
hand, in practice a domain expert typically knows a good global threshold
which is sufficient in most regions. Only few regions require a modified
threshold in order to detect the structures as demonstrated in [10]. The idea
of adapting a global threshold locally based on features was implemented in
[11], where the authors aim for a local adaption based on planar structure
detection. However, their approach requires two additional hyperparameters and
an according tuning procedure while only planar features influence the result
and other structures cannot be detected.

In order to overcome these limitations, our method focusses on allowing
adaption by multiple features that can be chosen at will and problem-dependent
and works without the need for feature-dependent hyperparameter tuning.

##  3\. Local Thresholding as an Optimization Problem

Our method is based on and trained from user input that is provided
interactively in such a way that several voxels are marked to identify
critical regions where the threshold needs be adapted. Let $V$ be a volume of
dimensions $\bm{d}$ as in Definition 1.1. Let $S\subseteq V$ be a set of _seed
voxels_ , selected at $M:=\\#S\ll\\#V$ critical positions. Around these voxels
we extract local environments $U_{j}$, $j=1,\ldots,M$, of an application-
dependent size $K\times K\times K$ where $K>1$ is odd. The size of the
environments determines the features and depends on the image, in particular
its resolution. By $F$ we denote the _feature function_ which maps local
environments onto a $d$-dimensional feature vector. Examples of such features
can be found in [12]. In our application, $F$ is chosen depending on the
dataset and includes structural information derived from the local
distribution of grayscale values as well as geometric information encoding the
similarity of local environments to primitives including lines and planes. It
should be emphasized that _any_ set of local features can be integrated in our
approach. Finally, a global threshold $\theta_{g}\geq 0$ needs be provided
which should be chosen such that it selects most of the object that shall be
segmented – in plain words, it should be reasonable.

Within a local environment, we shall consider a local threshold.

######  Definition 3.1.

For $\theta_{g}\geq 0$ and weights $\bm{\beta}\in\mathbb{R}^{d}$, the
(weighted) _local threshold_ for a region $U$ is defined as

(2) $\theta(U)=\theta_{g}+\bm{\beta}^{T}F(U).$

######  Remark 3.1.

With mask-based processing, extracting a full voxel environment around each
individual voxel becomes impossible at the borders of the volume. Classical
workarounds include periodic extension, constant padding, repeating or
mirroring the border voxel values or simply not processing them at all. In our
application, we decided on the latter one and set the voxel values at the
according positions explicitly zero.

We want to choose $\bm{\beta}$ such that the generated local thresholds are as
close to optimal local thresholds in the critical regions. To that end, we
first compute the features $F$ and estimate a local optimal binarizing
threshold $\theta^{*}$ in the regions $U_{j}$, $j=1,\ldots,M$. In our concrete
application, we specifically chose _Minimum Cross Entropy Thresholding_ [13]
for $\theta^{*}$, which basically computes the optimal threshold according to
the cross entropy loss for binary classification using a histogram-based
procedure. Putting everything together, we want our local thresholds to be
close to the optimal ones given the parameters. To that end, define

$\displaystyle\bm{\mathcal{F}}=\begin{bmatrix}F(U_{1})^{T}\\\ \vdots\\\
F(U_{M})^{T}\end{bmatrix}\quad\text{and}\quad\bm{\Theta}=\begin{bmatrix}\theta^{*}(U_{1})-\theta_{g}\\\
\vdots\\\ \theta^{*}(U_{M})-\theta_{g}\end{bmatrix},$

and compute the optimal feature weights $\bm{\beta}$ as the solution of the
minimization problem

$\operatorname*{argmin}_{\bm{\beta}}\frac{1}{2}\|\bm{\mathcal{F}}\bm{\beta}-\bm{\Theta}\|_{2}^{2}.$

To make the model more robust, we introduce elastic net regularization [14] to
this least squares problem, see (3). This is known to reduce the risk of
overfitting and only important features may adapt the threshold. A trade-off
between both effects is achieved by tuning its hyperparameters
$\lambda>0,\mu\in(0,1)$. Finally, we observe that so far we would deal with an
unconstrained optimization problem. However, if the feature weights evolve in
a way such that the produced local thresholds are always negative, we would
segment every voxel regardless of our initial goal. To avoid this, we
constrain the weights such that each local threshold is valid on the training
regions. We call a threshold valid if it lies within the admissible grayscale
interval $[0,W]$ where $W$ is the maximal representable voxel value depending
on the data type, thus preventing thresholding with unreasonable values. In
matrix form, define

$\displaystyle\bm{C}=\begin{bmatrix}-\bm{\mathcal{F}}\\\
\phantom{+}\bm{\mathcal{F}}\end{bmatrix}\quad\text{and}\quad\bm{b}=\begin{bmatrix}\;\;\phantom{(W-}\theta_{g}\bm{1}\\\
(W-\theta_{g})\bm{1}\ \end{bmatrix}$

which yields a closed convex polytope
$\mathcal{C}=\\{\bm{x}\in\mathbb{R}^{d}\mid\bm{Cx}\leq\bm{b}\\}$.

Our final optimization problem for finding the best feature weights is given
as

(3)
$\begin{split}\operatorname*{argmin}_{\bm{\beta}}\quad&\frac{1}{2}\|\bm{\mathcal{F}\bm{\beta}}-\bm{\Theta}\|_{2}^{2}+\lambda\left(\frac{1-\mu}{2}\|\bm{\beta}\|_{2}^{2}+\mu\|\bm{\beta}\|_{1}\right)\\\
s.t.\quad&\bm{C\bm{\beta}}\leq\bm{b}.\end{split}$

###  3.1. Solving the Problem

We observe that the optimization problem (3) can be decomposed into

$\operatorname*{argmin}_{\bm{\beta}}f(\bm{\beta})+g(\bm{\beta})+\iota_{\mathcal{C}}(\bm{\beta}),$

where

$\displaystyle f(\bm{\beta})$
$\displaystyle=\frac{1}{2}\|\bm{\mathcal{F}}\bm{\beta}-\bm{\Theta}\|_{2}^{2}+\frac{\lambda(1-\mu)}{2}\|\bm{\beta}\|_{2}^{2},$
$\displaystyle g(\bm{\beta})$ $\displaystyle=\lambda\mu\|\bm{\beta}\|_{1},$
$\displaystyle\iota_{\mathcal{C}}(\bm{\beta})$
$\displaystyle=\begin{cases}0,&\bm{\beta}\in\mathcal{C},\\\
+\infty,&\text{otherwise}.\end{cases}$

In this decomposition, the function $f$ is differentiable and convex while $g$
and $\iota_{\mathcal{C}}$ are convex. It is easy to see that all functions are
proper and lower-semicontinuous as well. Therefore, the problem can be solved
using the _proximal gradients_ method, see [15]. To apply them on (3), we need
explicit formulations of proximal operators which can then be interpreted as
gradient steps for convex but nonsmooth functions. In the following, we will
derive a proximal step for each of the three convex functions and combine them
into a solver for (3).

####  3.1.1. The Individual Descent Steps

Since the convex function $f$ is differentiable, its gradient is given
explicitly by

(4) $\nabla
f(\bm{x})=\bm{\mathcal{F}}^{T}\left(\bm{\mathcal{F}}\bm{x}-\bm{\Theta}\right)+\lambda(1-\mu)\bm{x},$

which is linear and thus Lipschitz continuous in $x$.

Concerning the nonsmooth parts of our objective function, we consider their
proximal operators, which, according to [15] are defined as

$\operatorname{prox}_{h}(\bm{x})=\operatorname*{argmin}_{\bm{z}}\frac{1}{2}\|\bm{x}-\bm{z}\|_{2}^{2}+h(\bm{z})$

for a proper lower-semicontinuous function $h$. For our particular function
$g$, it is known that the according proximal operator is a scaled _soft-
thresholding_ function, cf. [16].

######  Definition 3.2.

For $\theta\geq 0$, define _soft-thresholding_ with respect to $\theta$ as

$\displaystyle S_{\theta}\colon\mathbb{R}$ $\displaystyle\to\mathbb{R},$
$\displaystyle x$
$\displaystyle\mapsto\operatorname{sgn}(x)\,\max\\{0,|x|-\theta\\}.$

For the indicator function $\iota_{\mathcal{C}}$, on the other hand, the
associated proximal operator is given by the projection onto the polytope
$\mathcal{C}$ since

$\displaystyle\operatorname{prox}_{\iota_{\mathcal{C}}}(\bm{x})$
$\displaystyle=\operatorname*{argmin}_{\bm{z}}\frac{1}{2}\|\bm{x}-\bm{z}\|_{2}^{2}+\iota_{\mathcal{C}}(\bm{z})$
$\displaystyle=\operatorname*{argmin}_{\bm{z}\in\mathcal{C}}\frac{1}{2}\|\bm{x}-\bm{z}\|_{2}^{2}=\mathcal{P_{C}}(\bm{x}).$

In lack of a closed-form solution for the projection onto a convex polytope in
general, we use Hildreth’s method for inequalities [17, p. 283] to compute the
projection iteratively.

####  3.1.2. Choosing the step size

The final ingredient to iteratively train the FAITH model is the step size
whose choice it is a well-discussed topic in literature. This includes
constant step size, finding the best one in each iteration by a line search
[18] or accelerations including momentum methods [19]. For simplicity, we
choose a constant step size $\delta=L^{-1}$ where $L$ denotes a Lipschitz
constant of the gradient of $f$, but we emphasize that our method can also be
enhanced with the techniques mentioned above.

By (4), we have that

$\displaystyle\|\nabla f(\bm{x})-\nabla
f(\bm{y})\|\leq\|\bm{\mathcal{F}}^{T}\bm{\mathcal{F}}+\lambda(1-\mu)\bm{I}\|_{2}\|\bm{x}-\bm{y}\|.$

Since adding a nonnegative multiple of the identity matrix to the positive
semidefinite $\bm{\mathcal{F}}^{T}\bm{\mathcal{F}}$ only shifts the
eigenvalues, we note that
$\|\bm{\mathcal{F}}^{T}\bm{\mathcal{F}}+\lambda(1-\mu)\bm{I}\|_{2}=\|\bm{\mathcal{F}}^{T}\bm{\mathcal{F}}\|_{2}+\lambda(1-\mu)$
and consequently

$\displaystyle\|\bm{\mathcal{F}}^{T}\bm{\mathcal{F}}+\lambda(1$
$\displaystyle-\mu)\bm{I}\|_{2}\|\bm{x}-\bm{y}\|$
$\displaystyle=\left(\|\bm{\mathcal{F}}^{T}\bm{\mathcal{F}}\|_{2}+\lambda(1-\mu)\|\bm{I}\|_{2}\right)\|\bm{x}-\bm{y}\|$
$\displaystyle=\underbrace{\left(\operatorname{Eig}_{\max}(\bm{\mathcal{F}}^{T}\bm{\mathcal{F}})+\lambda(1-\mu)\right)}_{=:L}\|\bm{x}-\bm{y}\|,$

where $\operatorname{Eig}_{\max}$ denotes the maximal eigenvalue of its
argument matrix. Note that $L>0$ since $\bm{\mathcal{F}}^{T}\bm{\mathcal{F}}$
is positive semi-definite and $\lambda>0$ and $0<\mu<1$ holds.

####  3.1.3. Putting it Together

The basic proximal gradient method employs _forward-backward splitting_ [16]
which performs a gradient descent step for the differentiable part and a
proximal step for the nonsmooth part. Motivated this idea, one may be tempted
to pursue a _forward-backward-backward_ iteration of the form

$\displaystyle\begin{cases}\bm{\beta}^{(0)}\in\mathbb{R}^{d},&\\\
\bm{\beta}^{(k+1)}=\mathcal{P_{C}}\left(S_{\delta\lambda\mu}\left(\bm{\beta}^{(k)}-\delta\nabla
f\left(\bm{\beta}^{(k)}\right)\right)\right).&\end{cases}$

While this iteration converges linearly to a unique fixed point, the solution
obtained this way is not necessarily the optimal solution of Problem (3). This
can only be guaranteed provided that

(5) $\operatorname{prox}_{\delta\iota_{\mathcal{C}}+\delta
g}=\operatorname{prox}_{\delta\iota_{\mathcal{C}}}\circ\operatorname{prox}_{\delta
g}$

is fulfilled, in which case the following equivalences hold:

$\displaystyle 0$ $\displaystyle\in\nabla f(\bm{x}^{*})+\partial
g(\bm{x}^{*})+\partial\iota_{\mathcal{C}}(\bm{x}^{*})$
$\displaystyle\Leftrightarrow\;\bm{x}^{*}$
$\displaystyle=\operatorname{prox}_{\delta\iota_{\mathcal{C}}+\delta
g}\left(\bm{x}^{*}-\delta\nabla f(\bm{x}^{*})\right)$
$\displaystyle\Leftrightarrow\;\bm{x}^{*}$
$\displaystyle=\left(\operatorname{prox}_{\delta\iota_{\mathcal{C}}}\circ\operatorname{prox}_{\delta
g}\right)\left(\bm{x}^{*}-\delta\nabla f(\bm{x}^{*})\right)$
$\displaystyle\Leftrightarrow\;\bm{x}^{*}$
$\displaystyle=\mathcal{P}_{\mathcal{C}}\left(S_{\delta\lambda\mu}\left(\bm{x}^{*}-\delta\nabla
f(\bm{x}^{*})\right)\right)$

Then, the naive fixpoint iteration converges and the fixpoint is an optimal
solution to our problem. However, (5) is not always fulfilled. For a
counterexample, consider $\mathcal{C}=\\{(x,y)^{T}\in\mathbb{R}^{2}\mid
y\leq-2x\\}$, $\bm{\mathcal{F}}=\bm{I}$, $\bm{\Theta}=(1,3)^{T}$, $\lambda=1$
and $\mu=1/2$. Let $\bm{p}=(1,3)^{T}$. Then, $\delta=L^{-1}=2/3$ and we
observe that

$\displaystyle\operatorname{prox}_{\iota_{\mathcal{C}}+g}(\bm{p})=\begin{bmatrix}-0.4\\\
0.8\end{bmatrix}\neq\begin{bmatrix}-0.9\\\
1.9\end{bmatrix}=\operatorname{prox}_{\iota_{\mathcal{C}}}\left(\operatorname{prox}_{g}(\bm{p})\right).$

To avoid this problem, we incorporate a nested optimization scheme as
introduced in [20], and choose the following parameters:

  * •

$(\gamma_{n})_{n\in\mathbb{N}}=\delta=L^{-1}$ with $L$ as above

  * •

$(\lambda_{n})_{n\in\mathbb{N}}=1$

  * •

$\tau=1$

The procedure is summarized in Algorithm 1. We say that the algorithm has
converged if the weights $\bm{\beta}$ become stationary, i.e., if
$\|\bm{\beta}^{(k+1)}-\bm{\beta}^{(k)}\|_{2}<\epsilon$ for a small positive
number $\epsilon$.

Function  _FAITH_Training(_$\bm{\mathcal{F}}$ , $\theta_{g}$, $\lambda$,
$\mu$_)_

Input : Feature matrix $\bm{\mathcal{F}}\in\mathbb{R}^{M\times d}$

from seed voxel selection

Input : Global threshold $\theta_{g}\geq 0$

Input : Regularization parameters $\lambda>0,\mu\in(0,1)$

Output : Feature weight vector $\bm{\beta}\in\mathbb{R}^{d}$

$\bm{C}\leftarrow\begin{bmatrix}-\bm{\mathcal{F}}\\\
\phantom{+}\bm{\mathcal{F}}\end{bmatrix}$

$\bm{b}\leftarrow\begin{bmatrix}\;\;\phantom{(W-}\theta_{g}\bm{1}\\\
(W-\theta_{g})\bm{1}\ \end{bmatrix}$

$\delta\leftarrow\left(\operatorname{Eig}_{\max}(\bm{\mathcal{F}}^{T}\bm{\mathcal{F}})+\lambda(1-\mu)\right)^{-1}$

$\bm{\beta}\leftarrow\bm{0}$

while  _$\bm{\beta}$ not converged_ do

$\bm{x}\leftarrow\bm{\beta}-\delta\nabla f(\bm{\beta})$

$\bm{z}\leftarrow 2S_{\delta\lambda\mu}(\bm{x})-\bm{x}$

while  _$\bm{z}$ not converged_ do

$\hat{\bm{z}}\leftarrow\mathcal{P_{C}}\left(\frac{1}{2}(\bm{z}+\bm{x})\right)$

$\bm{z}\leftarrow\bm{z}+S_{\delta\lambda\mu}(2\hat{\bm{z}}-\bm{z})-\hat{\bm{z}}$

$\bm{\beta}\leftarrow\hat{\bm{z}}$

// The last value of $\hat{\bm{z}}$

return _$\bm{\beta}$_

Algorithm 1 Iterative solver for Problem (3).

Using the techniques from [20, Proposition 4.2] and taking that the polytope
$\mathcal{C}$ is always nonempty as it contains at least the feasible point
$\bm{0}$, the nested iteration can be shown in a straightforward way to
converge to the optimal solution.

######  Theorem 3.1.

The sequence $\bm{\beta}^{(k)}$ generated by Algorithm 1 converges to a
solution of (3).

###  3.2. Hyperparameter Tuning

Our thresholding model contains two hyperparameters, i.e., parameters not
optimized by the solver, namely, the regularization parameters $\lambda>0$ and
$\mu\in(0,1)$. In order to tweak them we use a _Grid Search_ approach.

The hyperparameter $\mu$ controls the trade-off between sparsity and
smoothness. The closer $\mu$ approaches $1$, the more focus is laid on
sparsity while denser solutions are obtained as $\mu$ becomes zero. In the
practical application we use the discrete parameter set
$P_{\mu}=\\{0.25,0.33,0.42,0.50,0.58,0.67,0.75\\}$ and omit $\mu=1$ in order
to avoid singularities during the computation of the step size $\delta$.

Regarding $\lambda$ we apply the approach presented in [21] where the maximum
meaningful value is given by
$\lambda_{\max}(\mu)=\mu^{-1}\|\bm{\mathcal{F}}^{T}\bm{\Theta}\|_{2}$. Then, a
regularization path is constructed in log-space resulting in the parameter set
$P_{\lambda}=\\{\epsilon\lambda_{\max}(\mu)10^{\frac{k}{k_{\max}-1}\log_{10}(\epsilon^{-1})}\\}_{k=0}^{k_{\max}-1}$
containing $k_{\max}$ values. Experimentally, we used $k_{\max}=16$ and a
small $\epsilon>0$.

The overall hyperparameter grid is given as $P=P_{\lambda}\times P_{\mu}$. In
our application, we used $K$-fold cross validation to select the best
parameters out of this fixed set.

###  3.3. Segmenting Big Volumes

Based on the training procedure, we can now formulate a segmentation
procedure. To that end, we consider an input volume of dimensions
$\bm{d}\in\mathbb{N}^{3}$ with voxels at positions $\bm{\alpha}\leq\bm{d}$ and
an output volume of identical dimensions with voxel values
$\widetilde{x}_{\bm{\alpha}}$. The method is outlined in Algorithm 2. We
assume that a user, ideally domain expert, interactively selected $M$ seed
voxels in critical regions $U_{1},\dots,U_{M}$ and furthermore provided a
global threshold $\theta_{g}$ that binarizes most of the components under
investigation well. Depending on the actual application, the user may also
provide a selection of (geometric) features to use, but they could also be
determined automatically, cf. [12]. In the first step, we extract local
environments around the selected seed voxels and compute the feature vectors
on these regions to build the feature matrix $\bm{\mathcal{F}}$. Then, a grid
search determines the best pair of hyperparameters which is used for training
our FAITH model and obtaining feature weights $\bm{\beta}$.

Finally, for the eventual segmentation we iterate (possibly in parallel) over
the input volume. For each voxel we extract a local voxel environment around
it and compute the same set of features with proper handling of boundary
voxels, cf. Remark 3.1. The result is combined with the trained feature
weights and the global threshold in order to compute a localized threshold
$\theta$. The value of the voxel in the target volume at the same position as
the input volume is given as the result of binarizing thresholding with that
local threshold.

Function  _FAITH_Segmentation(_$V,S,K,F,\theta_{g}$_)_

Input : Input volume $V$

Input : Seed voxel collection $S\subseteq V$, $\\#S=M$

Input : Environment size $K\in 2\mathbb{N}+1$

Input : Feature computation function $F$

Input : Global threshold $\theta_{g}\geq 0$

Output : Output volume $\widetilde{V}$

$\\{U_{j}\\}_{j=1}^{M}\leftarrow$ extract $K\times K\times K$ environment

around seed voxels $S$

$\bm{\mathcal{F}}\leftarrow\begin{bmatrix}F(U_{1})\\\ \vdots\\\
F(U_{M})\end{bmatrix}$

$(\lambda^{*},\mu^{*})\leftarrow$ determine by grid search

$\bm{\beta}\leftarrow$
FAITH_Training(_$\bm{\mathcal{F}},\theta_{g},\lambda^{*},\mu^{*}$_)

for  _$\bm{\alpha}$ in $V$_ do

$U\leftarrow$ $K\times K\times K$ environment around $\bm{\alpha}$

$\theta\leftarrow\theta_{g}+\bm{\beta}^{T}F(U)$

$\widetilde{x}_{\bm{\alpha}}\leftarrow T_{\theta}(x_{\bm{\alpha}})$

Algorithm 2 Segmentation using FAITH

###  3.4. Runtime and Memory Analysis

For large voxel volumes, only algorithms with linear runtime in the number of
voxels are admissible in practice. Therefore, we briefly analyze the runtime
and memory requirements of our thresholding procedure.

Concerning the runtime, the extraction of local environments around the seed
voxels has a runtime of $\mathcal{O}(M)$ where $M$ denotes the number of seed
voxels. The training itself consists of a nested solver loop with $m$
iterations of the outer loop and $k_{j},j=1,\ldots,m$, the associated inner
iterations. With $k=\sum_{j=1}^{m}k_{j}$, a single FAITH training has a
runtime complexity of $\mathcal{O}(k)$. Each iteration depends on the number
of seed voxels $M$ in some polynomial way, however since $M$ is typically very
small and, more important, _independent_ of the number of voxels in the
volume, the according factor will be so as well. Aggregating the runtimes of
the training involving a grid search over $\\#P$ parameters using $t$ threads
and the last training with the found hyperparameters, we obtain
$\mathcal{O}(k(1+\frac{\\#P}{t}))$. The final step involves a single pass
through the voxel volume which is clearly linear in the number $N$ of voxels.

Overall, the runtime complexity of Algorithm 2 can thus be estimated as

$\mathcal{O}\left(M+k\left(1+\frac{\\#P}{t}\right)+N\right).$

Already for practical reasons, the number of seed voxels $M$ is typically very
small (since they have to be marked manually) and independent of $N$, thus
asymptotically yielding an effort which is linear with respect to the number
of voxels $N$.

Considering memory requirements, we notice that during training we need to
keep the feature matrix, the polytope constraints and of course the solution
vector in memory. The feature matrix $\bm{\mathcal{F}}$ is of size $M\times
d$, where $d$ is the dimensionality of the feature vector. Likewise, the
polytope constraints consist of a matrix $\bm{C}$ of size $2M\times d$ and a
vector $\bm{b}$ of size $2M$. The solution vector $\bm{\beta}$ has
dimensionality $d$. Thus, the overall space complexity for training scales
with $Md$. The classification phase only relies on local environments of fixed
size and the trained solution vector, thus having constant memory complexity.
Fortunately, the feature vector dimensionality is constant after feature
selection and thus the memory requirements scale linearly with the number of
seed voxels which is assumed independent of the number of voxels, making our
segmentation procedure especially well suited for handling large three-
dimensional datasets.

##  4\. Results

In this section we demonstrate the capabilities of our algorithm to detect
geometric structures not captured by global thresholding by means of two
examles. Figure 1(a) shows a rendering of the head section of a Peruvian mummy
now located at the Lindenmuseum in Stuttgart, while Figure 3(a) shows a
computed tomography scan of a wolf jaw labeled ”Canis Lupus”. Both scans were
generated by the Fraunhofer Development Center for X-ray Technology in Fürth.

Our first aim was to segment the skull of the mummy without capturing the
wrappings around it. Doing so, we used the global threshold specified in Table
1. In Figure 1(c) we see that global thresholding results in holes at the top
of the eye sockets, whereas lowering that threshold would result in segmenting
the wrappings too. We applied FAITH by interactively selecting 54 seeds out of
104,368,576 total voxels in these critical regions and set the parameters as
in Table 1, using the _same_ global threshold. The result is given in Figure
1(d) with a clearly visible improvement in the critical regions. At the same
time, the rest of the skull which was detected properly by the global
threshold stays unaffected. Thus, the _planar_ structures of the eye socket
are detected by the features quite well and the segmentation result improved
considerably. As a side note we like to demonstrate the influence of our
modifications to the basic least squares approximation. The differences can be
observed in Figure 2. The least squares problem without regularization is
rendered ill-conditioned if a feature produces the very same values for
multiple environments, resulting in a volume cluttered with missegmentations.
Regularization and restricting to valid thresholds improves this to the known
result.

We also applied our procedure to the wolf jaw scan. Here, we specified the
threshold in a way such that the teeth are kept as good as possible, while the
jaw bone shall be discarded. Unfortunately, binarization using a global
threshold also discards most of the teeth, cf. Figure 3(c). Again, we
interactively selected critical regions, set the FAITH parameters as specified
in Table 1 and applied the segmentation method. Here, we selected 166 out of
2,467,050,300 total voxels. The result is depicted in Figure 3(d) in which the
teeth are detected better. While individual voxels of the jaw bone remain,
these can be easily removed by simple postprocessing.

The execution times of these applications are summarized in Table 2. The
implementation is within a Fraunhofer software framework and runs exclusively
on the CPU; the measurements were recorded on an Intel® Core™ i7-770H
processor with eight logical cores and an average clock rate of 4.2 GHz. While
the procedure is algorithmically efficient in the sense that its runtime is
linear with respect to the number of voxels, the cubic increase of the number
of voxels with respect to resolution makes us propose that in future work this
algorithm should be implemented on GPUs to accelerate this even further.

Scan | Threshold | Env. size | #Features
---|---|---|---
Canis Lupus | 24415 | 5 | 2
Mummy skull | 1541 | 7
Table 1. Experiment setup Scan | Size | Time
---|---|---
Mummy skull | 199 MiB | 1801.79 s
Canis Lupus | 4076 MiB | 3155.80 s
Table 2. Runtime measurements

(a) Mummy head

(b) Original data

(c) Binarization

(d) FAITH

Figure 1. Binarization applied to the mummy skull data in (1(b)) produces
holes at the top of the eye sockets (1(c)). FAITH is able to detect bone in
these critical sections while the overall segmentation remains good (1(d)).
Results are overlaid in white over the original data.

(a) Binarization

(b) Least Squares only

(c) FAITH

Figure 2. Applying global binarization fails to detect bone in the upper eye
socket regions (2(a)). FAITH without any kind of regularization and validity
constraints, i.e., using only a simple least squares approximation, produces a
very cluttered result (2(b)). The full procedure omits these problems and
shows the better segmented skull in (2(c)).

(a) Wolf jaw

(b) Original data

(c) Binarization

(d) FAITH

Figure 3. Binarization applied to a scan of wolf jaw labeled _Canis Lupus_ in
(3(b)) discards most of the teeth structure, see (3(c)). Our procedure detects
the teeth better while simultaneously discarding the jaw bone we wish to
ignore (1(d)).

##  5\. Conclusions

In this work we proposed FAITH, a novel thresholding technique which adapts a
global threshold locally on the basis of freely selectable features. The main
benefit is that a domain expert can interactively identify critical regions
where global thresholding produces undesirable results. Inside these regions,
features extract structural information and a model is trained to modify the
global threshold in a way such that the localized threshold is optimal inside
these regions. At the same time, the global one is modified only if the
trained structure is observed, thus in regions where the global threshold
suffices for segmentation, the detection quality remains the same. Overall,
this procedure allows improving the segmentation quality over global
thresholding interactively and at the same time handling three-dimensional
datasets without size restrictions due to purely local processing.
Furthermore, the same algorithm can be used for a variety of different domains
and applications as long as we process volumes and the object under
investigation can be segmented using a thresholding approach.

Acknowledgements This work was supported by the project ”Digitalisierung,
Verarbeitung und Analyse kultureller und industrieller Objekte: Wertschöpfung
aus großen Daten und Datenmengen - Big Picture” that has been promoted and
funded by the Bavarian State Government under Grant No. AZ.: 43-6623/138/2
from 2018 to 2021.

## References

  * [1] W. Niblack, _An Introduction to Digital Image Processing_. Birkeroed, Denmark, Denmark: Strandberg Publishing Company, 1985.
  * [2] J. Sauvola and M. Pietikäinen, “Adaptive document image binarization,” _Pattern Recognit._ , vol. 33, no. 2, pp. 225–236, 2000.
  * [3] D. Bradley and G. Roth, “Adaptive Thresholding using the Integral Image,” _J. Graph. Tools_ , vol. 12, pp. 13–21, 01 2007.
  * [4] J. Lifton and T. Liu, “An adaptive thresholding algorithm for porosity measurement of additively manufactured metal test samples via X-ray computed tomography,” _Addit. Manuf._ , vol. 39, p. 101899, 2021.
  * [5] A. J. Burghardt, G. J. Kazakia, and S. Majumdar, “A Local Adaptive Thresholding Strategy for High Resolution Peripheral Quantitative Computed Tomography of Trabecular Bone,” _Ann. Biomed. Eng._ , vol. 35, no. 10, pp. 1678–1686, 2007.
  * [6] J. Kittler, J. Illingworth, and J. Föglein, “Threshold selection based on a simple image statistic,” _Comput. Vis. Graph. Image Process._ , vol. 30, no. 2, pp. 125–147, 1985.
  * [7] M. Diwakar, Sonam, and M. Kumar, “CT Image Denoising Based on Complex Wavelet Transform Using Local Adaptive Thresholding and Bilateral Filtering,” in _Proceedings of the Third International Symposium on Women in Computing and Informatics_ , ser. WCI ’15, 2015, pp. 297––302.
  * [8] D. Y. Kim and J. W. Park, “Connectivity-Based Local Adaptive Thresholding for Carotid Artery Segmentation Using MRA Images,” _Image Vis. Comput._ , vol. 23, no. 14, pp. 1277––1287, 12 2005.
  * [9] F. H. Chan, F. Lam, and H. Zhu, “Adaptive Thresholding by Variational Method,” _IEEE Trans. Image Process._ , vol. 7, no. 3, pp. 468–473, 1998\.
  * [10] J. Michetti, A. Basarab, F. Diemer, and D. Kouame, “Comparison of an adaptive local thresholding method on CBCT and $\mathrm{\mu}$CT endodontic images,” _Phys. Med. Biol._ , vol. 63, no. 1, p. 015020, 2017.
  * [11] C.-F. Westin, A. Bhalerao, H. Knutsson, and R. Kikinis, “Using Local 3D Structure for Segmentation of Bone from Computer Tomography Images,” in _CVPR_ , 06 1997, pp. 794–800.
  * [12] T. Lang, “AI-Supported Interactive Segmentation of 3D Volumes,” Ph.D. dissertation, University of Passau, 07 2021.
  * [13] C. Li and C. Lee, “Minimum cross entropy thresholding,” _Pattern Recognit._ , vol. 26, no. 4, pp. 617 – 625, 1993.
  * [14] H. Zou and T. Hastie, “Regularization and variable selection via the elastic net,” _J. R. Stat. Soc., Series B_ , vol. 67, pp. 301–320, 2005.
  * [15] N. Parikh and S. Boyd, “Proximal Algorithms,” _Found. Trends Optim._ , vol. 1, no. 3, pp. 127–239, 01 2014.
  * [16] P. Combettes and V. R. Wajs, “Signal Recovery by Proximal Forward-Backward Splitting,” _Multiscale Model Simul._ , vol. 4, 01 2005.
  * [17] G. T. Herman and A. Lent, “Iterative reconstruction algorithms,” _Comput. Biol. Med._ , vol. 6, no. 4, pp. 273–294, 1976.
  * [18] S. Boyd and L. Vandenberghe, _Convex Optimization_. Cambridge University Press, 03 2004.
  * [19] D. E. Rumelhart, G. E. Hinton, and R. J. Williams, _Learning Representations by Back-Propagating Errors_. Cambridge, MA, USA: MIT Press, 1988, p. 696–699.
  * [20] C. Chaux, J.-C. Pesquet, and N. Pustelnik, “Nested Iterative Algorithms for Convex Constrained Image Recovery Problems,” _SIAM J. Imaging Sci._ , vol. 2, no. 2, pp. 730–762, 2009.
  * [21] R. Tibshirani, T. Hastie, and J. Friedman, “Regularized Paths for Generalized Linear Models Via Coordinate Descent,” _J. Stat. Softw._ , vol. 33, 02 2010\.