Integrating knowledge-based expert systems and advanced machine learning for object-based image analysis



Angelos Tzotsos, Demetre Argialas

Remote Sensing Laboratory, National Technical University of Athens

OSGeo Charter Member

OGC Member


GEOBIA 2014 Thessaloniki


Presentation outline

  • Introduction
  • Methodology:
    • Preprocessing
    • Image Segmentation
    • Machine Learning classification
    • Knowledge-based classification
  • Implementation
  • Conclusions

Introduction

Research goals

  • Investigate state-of-the-art machine learning methods in OBIA
  • Investigate novel computer vision methods in the context of OBIA
  • Integrate knowledge-based classification using pure expert system tools
  • Implement a free and open source (FOSS) framework for OBIA

GEOBIA

  • In Computer Vision, image analysis is considered in three levels: low, medium and high
  • Such approaches were implemented usually in separate software environments since low and medium level algorithms are procedural in nature, while high level is inferential
  • GEOBIA: Integration of image analysis levels

State-of-the-art

  • The last decade, the Object-Based Image Analysis paradigm has been the subject of very active research and has developed into a state-of-the-art methodology in remote sensing
  • Significant progress incorporating machine learning methods into classification of remotely sensed data
  • In the field of knowledge-based systems, recent research is focused on the representation of knowledge but also in the efficiency of reasoners and integration with other artificial intelligence systems

Methodology

Methodology

In this research, an object-based image analysis framework was developed integrating:

  • Advanced machine learning classifiers such as Support Vector Machine (SVM) and Relevance Vector Machines (RVM)
  • a Hybrid edge-based and region-based image segmentation algorithm (MSEG)
  • a Non-linear scale-space simplification algorithm (AML) and
  • a Knowledge-Based Expert System shell (CLIPS)

Preprocessing

Scale-space representation

  • Earth surface objects cannot be represented to a single scale but rather to many
  • Through isotropic multi-resolution analysis (by down-sampling the initial data), all linear scale space approaches present the same important drawback: image edges are blurred and new non-semantic objects may appear at coarse scales

Scale-space representation

Non-linear operators and non-linear scale spaces have been studied and applied in various image processing and computer vision applications

  • Following the pioneering work of Perona and Malik in 1990 there has been a flurry of activity in partial differential equation and anisotropic diffusion filtering techniques
  • Another way to produce non-linear scale spaces is through mathematical morphology and morphological levelings, which have been introduced by Meyer in 1998

Morphological Levelings

Properties of Morphological Levelings:

  • they do not produce new extrema at larger scales
  • they enlarge smooth zones and create new ones
  • they are particularly robust (strong morphological filters)
  • they do not displace edges
  • they are invariant to spatial translation, to rotation and to change of illumination

Anisotropic Morphological Levelings

  • The first step in the developed approach is the construction of the non-linear scale-space representation in order to elegantly simplify raw data
  • Anisotropic Morphological Levelings (AML) (Karantzalos et al 2007) were incorporated in the processing scheme
  • Anisotropic Morphological Levelings are a combination of morphological levelings with anisotropic markers and are employed in order to achieve better segmentation results by reducing the heterogeneity of image data, therefore reducing over-segmentation

Isotropic vs Anisotropic scale-space

usersusersusersusers

usersusersusersusers

Left to right: Original image, filtering scales 10, 50, 100

AML examples

users users users

Edge Feature Extraction

  • Extracting primitives (i.e. contours, edges, lines, etc) is a basic low-level operation in the human visual system
  • These primitives give important information about the geometric content of images
  • Many shapes can be described roughly or in detail with edge and line primitives
  • Here, edge information was obtained from the standard Canny detector and the state-of-the-art Line Segment Detector (LSD)

Canny over AML

users users users users

Left to right: Original image, AML scales 10, 50, 100

Advanced Edge Features

Line Segment Detector:

  • Starts by computing the level-line angle at each pixel to produce a level-line field.
  • This field is segmented into connected regions of pixels (support regions) that share the same level-line angle up to a certain tolerance
  • After examining if line support regions are aligned properly, a selection of meaningful rectangles is provided as the final result

LSD results

users users users

Left to right: Original image, LSD and Canny at scale 100 (AML)

Image Segmentation

MSEG

  • MSEG is a region-based multi-scale segmentation algorithm developed for object-oriented image analysis
  • Introduced in 2005 under GPL license
  • Starting from a pixel representation it creates objects through continuous pair-wise object fusions, executed in iterations (passes)
  • MSEG algorithm defines a cost function similar to eCognition
  • MSEG introduced enhancements for calculation of starting points, and was enhanced through texture and edge features

MSEG

users

MSEG

users

Edge-enhanced MSEG

  • The MSEG algorithm was improved in order to be able to integrate edge information (as a constrain) during the segmentation procedure
  • Iterative pairwise fusions occur within the image space, starting from single pixel objects, in a way that local heterogeneity is minimized (for color and shape criteria)
  • During this process the edge information is used as a boundary
  • After convergence, edge pixels remain unmerged
  • A last iteration of the algorithm is forced on edge objects only, and a selection is made, to which neighboring object they should be merged

Edge-enhanced MSEG results

users users users users

Left to right: Original image, Original MSEG, MSEG with Canny, MSEG with LSD at scale 50

Edge-enhanced MSEG with Canny

users users users

Left to right: Original image, Canny, edge-enhanced MSEG at scale 50

Edge-enhanced MSEG last iteration

users users

Left to right: converged edge-enhanced MSEG, final result after extra merging iteration

Edge-enhanced MSEG with LSD

users users users

Left to right: Original image, LSD, edge-enhanced MSEG at scale 50

Edge-enhanced MSEG - SAR

users users

Left to right: Original MSEG, edge-enhanced MSEG with Canny

Edge-enhanced MSEG - Hyperspectral

users users users

users users users

Top: Original CASI image, Mean-Shift, Watershed

Bottom: Original MSEG, MSEG with AML, edge-MSEG with AML

Feature extraction

Feature extraction

  • MSEG produces Labeled Image and a LabelMap representation
  • LabelMap is holding the object features (spectral, shape etc)
  • Objects are exported to vector (with attributes) using GDAL
  • Supported formats: SHP, PostGIS, SpatiaLite

Machine Learning Classification

Support Vector Machines

  • Support Vector Machine (SVM) is a sparse binary regression and classification methodology that has been shown to deliver great results, comparative with the best machine learning methods
  • SVM has been used in a variety of Remote Sensing applications, and has been shown to outperform other classification methods

Support Vector Machines

  • In 2006, the SVM methodology was introduced into the OBIA framework as a classifier of primitive image objects (Tzotsos 2006, 1st GEOBIA conference)
  • The SVM classifier seeks to find the optimal separating hyperplane between classes by focusing on the training data (support vectors) that are placed at the edge of the class descriptors
  • Training data other than support vectors are discarded
  • SVM outperforms traditional OBIA classification methods like the Nearest Neighbor classifier

Support Vector Machines

users

Support Vector Machines and Scale-Space

  • In 2011, an OBIA framework was introduced, eliminating the need for tuning several parameters during segmentation and classification

users

Relevance Vector Machines

  • Relevance Vector Machine (RVM) was introduced by Tipping in 2001
  • A novel approach to kernel-based regression and classification by extending the SVM using a probabilistic Bayessian approach
  • Recently, RVM has been used as a state-of-the-art machine learning method for Remote Sensing applications.
  • First results suggested that RVMs offer an excellent trade-off between accuracy and sparsity of the solution, and become less sensitive to the selection of the free parameters

Relevance Vector Machines in OBIA

  • Here, the RVM algorithm was implemented in C++ and integrated into the OBIA framework
  • The objects are obtained from the edge-enhanced MSEG algorithm
  • Image objects along with their computed features, formed the feature space of the RVM classification
  • A training set was given as input to the RVM training module
  • A trained RVM model which included the relevance vectors was obtained
  • All available image objects were evaluated by the trained classifier

RVM results

users users users

Left to right: Original multispectral image, LSD, edge-enhanced MSEG

RVM results

users

Image objects in QGIS

RVM results

users users

Left: SVM classification result (accuracy 91.34%)

Right: RVM classification result (accuracy 87.90%)

users

RVM results

users users users

Left to right: Original Landsat TM image, Canny, edge-enhanced MSEG

RVM results

users users

Left: SVM classification result (accuracy 87.64%)

Right: RVM classification result (accuracy 85.79%)

users

Knowlegde-based Expert System Classification

Knowlegde-based Expert Systems

In Artificial Intelligence, a Knowledge Based Expert System is a computer system designed to emulate the decision-making and problem-solving ability of a human expert in a narrow domain or discipline

Properties/Advantages of Expert Systems:

  • They simulate human reasoning about a problem domain, rather than simulating the domain itself
  • They perform reasoning over representations of human knowledge
  • They solve problems by heuristic or approximate methods
  • They provide ease of prototyping: rules can be added easily without modifying existing rules
  • They allow separate representation, but combined use, of knowledge pertaining to different domains

Expert System architecture

Expert Systems are composed by:

  • The knowledge base, which is a collection of facts (data) and rules derived from the human expert, typically represented as IF-THEN statements
  • The inference engine, the main processing element of the expert system that applies the rules to the known facts to deduce new facts
  • The user interface

OBIA methodology

Classification refinement is a well-established OBIA process. Here, this is implemented, by integrating:

  • A state-of-the-art machine learning classifier (RVM or SVM)
  • A full Expert System environment
  • A spatial RDBMS serving as the engine for the spatial analysis of image objects

OBIA methodology

  • MSEG provides primitive objects
  • Image objects (with attributes) are stored in a spatial database
  • A machine learning classifier is providing a first object classification
  • Classification results are stored in the databse
  • CLIPS rules are implemented
  • Knowledge-based classification is performed on the database objects
  • Final classification result is obtained

OBIA methodology

users

KBES results

users users

Left: SVM classification result (accuracy 91.34%)

Right: CLIPS re-classification result (accuracy 91.76%)

users

KBES results


(defrule fix-tile-roofs
        ?seg <- (object
                        (is-a IMG_OBJECT)
                        (mean-1 ?blue)
                        (compactness ?cmp)
                        (class-id 2)
                )
        (test (< ?blue 48.0))
        (test (> ?cmp 800.0))
        =>
        (send ?seg put-class-id 4)
)

(defrule fix-tile-roofs2
        ?seg <- (object
                        (is-a IMG_OBJECT)
                        (compactness ?cmp)
                        (class-id 2)
                )
        (test (> ?cmp 2000.0))
        =>
        (send ?seg put-class-id 4)
)

(defrule fix-tile-roofs3
        ?seg <- (object
                        (is-a IMG_OBJECT)
                        (mean-1 ?blue)
                        (class-id 2)
                )
        (test (< ?blue 34.0))
        =>
        (send ?seg put-class-id 4)
)
                

CLIPS knowledge base used

KBES results

users users

Left: SVM classification result (accuracy 87.64%)

Right: CLIPS re-classification result (accuracy 88.13%)

users

KBES results


(defrule fix-waterbodies1
        ?seg <- (object
                        (is-a IMG_OBJECT)
                        (class-id 4)
                        (mean-1 ?blue)
                        (mean-5 ?mir)
                        (mean-4 ?nir)
                )
        (test (< ?blue 70.0))
        (test (> ?mir 30.0))
        =>
        (send ?seg put-class-id 3)
)

(defrule fix-waterbodies2
        ?seg <- (object
                        (is-a IMG_OBJECT)
                        (class-id 4)
                        (mean-1 ?blue)
                        (mean-5 ?mir)
                        (mean-4 ?nir)
                )
        (test (> ?nir 130.0))
        (test (> ?mir 30.0))
        =>
        (send ?seg put-class-id 2)
)
                

CLIPS knowledge base used

Implementation

Implementation

The developed approach includes a three-tier software framework integrating:

  • The spatial RDBMS holding the vector information (PostGIS or SpatiaLite)
  • The object-oriented environment of the Python programming language and
  • A Pythonic wrapper (PyCLIPS) around the CLIPS Expert System C library

Implementation

MSEG exports CLIPS object definition based on computed features:


(defclass IMG_OBJECT (is-a USER) (role concrete)
        (slot id (type INTEGER))
        (slot area (type INTEGER))
        (slot perimeter (type INTEGER))
        (slot compactness (type FLOAT))
        (slot mean-1 (type FLOAT))
        (slot mean-2 (type FLOAT))
        (slot mean-3 (type FLOAT))
        (slot mean-4 (type FLOAT))
        (multislot neighbors)
        (slot class-id (type INTEGER))
        (slot classification (type SYMBOL))
)
                

Implementation

The developed algorithm reads all image objects (records) from the RDBMS tables creating a list of Python objects with their attributes in working memory:


def load_objects_from_database():
    conn = db.connect("segments.db")
    conn.row_factory = db.Row
    cur = conn.cursor()
    SQL = "select * from Level"
    cur.execute(SQL)
    while True:
        r = cur.fetchone()
        if not r:
            conn.close()
            break
        res = {
            'id': clips.Integer(r['ID']),
            'area': clips.Integer(r['AREA']),
            'perimeter': clips.Integer(r['PERIMETER']),
            'compactness': clips.Float(r['COMPACTNESS']),
            'mean-1': clips.Float(r['MEAN1']),
            'mean-2': clips.Float(r['MEAN2']),
            'mean-3': clips.Float(r['MEAN3']),
            'mean-4': clips.Float(r['MEAN4']),
            'class-id': clips.Integer(r['CLASS'])
        }
        c = clips.FindClass("IMG_OBJECT")
        i = clips.BuildInstance(str(r['ID']), c)
        for k in res.keys():
            i.Slots[k] = res[k]
                

Implementation

After the class instances are created in CLIPS, the knowledge base is loaded and the appropriate rules are fired:


clips.Load("rules.clp")
clips.Reset()
create_objects_from_database()
clips.Run()
save_classification_results_to_database()
                

Implementation

The resulting instances are then imported to the Python environment and the classification column is updated in the database with the new value from CLIPS. An example of a rule is presented, that will classify all vegetation objects by computing the NDVI index:


(defrule find-vegetation
        ?seg <- (object
                        (is-a IMG_OBJECT)
                        (mean-4 ?nir)
                        (mean-3 ?red)
                )
        (test (> (/ (- ?nir ?red) (+ ?nir ?red 0.0001)) 0.0))
        =>
        (send ?seg put-classification "Vegetation")
        (send ?seg put-class-id 1)
)
                

Implementation

A great advantage of the implemented software is the ability to perform native, multi-level spatial queries to the spatial RDBMS and then use the result for inference within the expert system environment:


(defrule find-vegetation-intersecting
        ?seg <- (object
                        (is-a IMG_OBJECT)
                        (id ?id)
                )
        (test (> (python-call py_find_vegetation ?id) 0))
        =>
        (send ?seg put-classification "Vegetation")
)
                

Implementation

The Python function for intersecting in PostGIS:


def py_find_vegetation(id):
    con = psycopg2.connect(database='testdb', user='user') 
    cur = con.cursor()
    SQL = "SELECT ST_Intersection(cur.the_geom,ab.the_geom), cur.id " 
    "FROM level_one as cur, level_two as ab WHERE cur.id = '%s'" 
    "AND ab.class = 'Vegetation'" % (str(id))
    cur.execute(SQL)          
    r = cur.fetchone()
    if r:
        return 1
    else:
        return 0
                

Conclusions

Conclusions

  • RVM was introduced for OBIA applications
  • RVM showed promising results, of almost equal quality with the SVM classifier
  • RVM was shown to be very sparse and faster in prediction performance from SVM
  • RVM is independent of parameter tuning
  • SVM outperformed RVM in classification accuracy
  • An important feature of RVM is the probabilistic output, which can be integrated with other classification methods that can handle uncertainty

Conclusions

  • Integration of an Knowledge-Based Expert System tool for object-based image classification
  • An expert system tool has the advantage of being very generic and easily extended
  • CLIPS was extended to use spatial operators, though integration with spatial database systems and an object-oriented programming language (Python)

Conclusions

  • The integration of human knowledge into an image analysis framework can refine and improve results, even with a small number of rules and heuristics by the expert user
  • A full expert system application would need to include far more in rule numbers and complexity
  • Integrating machine learning and knowledge-based systems is a very promising OBIA methodology and can provide high quality results

Future work

  • Investigation of expert systems and OBIA for complex remote sensing applications
  • Comparison of RVM and SVM with other state-of-the-art machine learning algorithms such as ensembles and random forests
  • Evaluation of fuzzy SVMs
  • Investigation of unsupervised learning methods

Getting Involved

Source Code, Wiki, Issues on GitHub

https://github.com/kalxas/mseg


https://github.com/kalxas/cvAML


Acknowledgments

This research has been co-financed by the European Union (European Social Fund-ESF) and Greek national funds through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF)-Research Funding Program: THALES: Reinforcement of the interdisciplinary and/or inter-institutional research and innovation.

Thank you

Questions?