- In this paper, we propose the application of rulebased reasoning for knowledge assisted image segmentation and object detection. A region merging approach is proposed based on fuzzy labeling and not on visual descriptors, while reasoning is used in evaluation of dissimilarity between adjacent regions according to rules applied on local information.
Index Terms— Knowledge-assisted analysis, rule-based reasoning, semantic region merging.
A ing task in computer vision and one of the most crucial
UTOMATIC segmentation of images is a very
challengsteps toward image understanding. Although a great effort
has been consumed in designing generic, robust and efficient
segmentation algorithms [
Knowledge assisted analysis can be defined as a tightly coupled and constant interaction between low level image analysis and higher level knowledge. In this paper we propose an algorithm that involves simultaneously both segmentation and detection of simple objects. Starting from traditional graph-based segmentation, the proposed technique continues with fuzzy region labeling and semantic region merging. More specifically the latter is based on rule-based reasoning, using knowledge about the possible labels of the candidate for merging regions and of their direct neighbors, to improve the initial segmentation and labeling.
To perform rule-based reasoning, we use the expert system
NEST [
IF condition THEN conclusion (w)
where condition is a conjunction of propositions, conclusion
is a single proposition and weight w expresses the uncertainty
of the conclusion if the condition is true. During consultation,
all rules for which the condition is true with some positive
degree (weight) are activated and their contributions are used
to compute the weights of goals.
II. INITIAL SEGMENTATION AND REGION LABELING
Our intention is to operate on a higher level of information
where image regions are linked to possible labels rather than
only to their visual features. For the representation of an image
we adopt the Attributed Relational Graph (ARG) [
Based on these features and the adjacency information
provided by the ARG, the target is to assign to each region a a
fuzzy set of labels La. In order to achieve this (for more details
please refer to previous work in [
This section presents the integration of a rule based reasoning system into an image segmentation algorithm. Based on the foundations described in the previous section, we introduce a novel segmentation algorithm that relies on fuzzy region labeling and rules to solve the problem of image oversegmentation.
Recursive Shortest Spanning Tree, or simply RSST, is a bottom-up segmentation algorithm that begins from the pixel level and iteratively merges neighbor regions according to a distance value until certain termination criteria are satisfied. This distance is calculated based on color and texture characteristics, which are independent of the area’s size. In every step the two regions with the least distance are merged; visual characteristics of the new region are extracted and all distances are updated accordingly.
We introduce here a modified version of RSST, called
Semantic RSST (S-RSST) that aims to improve the usual
oversegmentation results by incorporating region labeling in
the segmentation process [
Let us now examine in detail one iteration of the SRSST algorithm. Firstly, the edge eab with the least weight is selected, then regions a and b are merged. Vertex vb is removed completely from the ARG, whereas va is updated appropriately. This update procedure consists of the following two actions: 1) Re-evaluation of the degrees of membership of the labels fuzzy set in a weighted average (w.r.t. the regions’ size) fashion. 2) Re-adjustment of the ARG edges by removing edge eab and re-evaluating the weight of the affected edges invoking NEST.
This procedure continues until the edge e∗ with the least weight in the ARG is bigger than a threshold: w(e∗) > Tw. This threshold is calculated in the beginning of the algorithm, based on the histogram of all weights in E.
Expert system NEST serves in knowledge-assisted analysis as an estimator for the dissimilarity of two adjacent regions a and b in the image. The input consists of the fuzzy sets La and Lb of the two regions, with membership functions μA and μB respectively as well as the fuzzy set of their direct neighbors. More specifically, we consider as direct neighbors only the four dominant directional neighbors of regions a and b (north, south, west, east). With this input, NEST is able to reason about the (dis)similarity between two adjacent regions, according to rules applied on local information of what each region might represent given its neighborhood. The rule base is structured into two layers. The first layer determines the dominant label(s) of the regions according to the initial labeling of regions and their neighbors; the confidence of the initial labeling (expressed in these rules as ”high”, ”medium”, ”low”) is derived from the initial fuzzy labels. This layer contains 60 rules; a rule for each combination of label, of its confidence, of the region and its neighbor. The next layer increases/decreases the similarity of regions a and b if they share/don’t share the same dominant label. This layer contains 48 rules; a rule for each combination of possible dominant labels of the two regions. All rules have been created empirically, by a knowledge engineer. Example rules for the first and second layer look like follows:
IF A conf sky(medium) AND A conf sea(medium) AND A conf sand(low) AND leftofA conf sky(high) AND rightofA conf sky(high) THEN A dominant(sky) (0.8) IF A dominant(sky) AND B dominant(sky,sea)
THEN A B similar (0.7)
Inferred weight of the (dis)similarity proposition is used to drive segmentation based on semantic information and to resolve oversegmentation problems.
We will illustrate the rule-based reasoning step on a following simple example. Let 0, 2, 3, 7, 8 be five regions of an exemplar image of a beach scene, where 0, 2, 3, 8, are adjacent to 7. Table I illustrates the associated fuzzy set of each region, i.e. the degrees of membership of each concept. Correct concepts for each region, according to the ground truth, are highlighted with bold letters.
From this input, the rule base infers as dominant labels Sea and Person for 0, Sea and Sky for 2, Person and Sky for 3, Sea and Sky for 7, and Sea for 8. This will result in the following ordering of region pairs according to their similarity: 7-2 (most similar), 7-8, 7-0 (less similar), 7-3 (most dissimilar); 47 rules have been activated during this inference. Thus the regions 7 and 2 will be merged in this iteration of the S-RSST algorithm.
The methodology presented in this paper aimed in improving image segmentation based on initial labeling of regions and not only on visual features. This hybrid algorithm involves ruled-based reasoning in a region merging process, by means of calculating the semantic distance between two adjacent regions based on local knowledge. First experiments have shown the feasibility of our approach, nevertheless the current rule base must be thoroughly tested. In our future work, we will incorporate also some domain knowledge (e.g. sea cannot be above sky) to improve the whole process.
This research was supported by the European Commission under contract FP6-027026 K-SPACE. Thanos Athanasiadis is funded by the Greek Secretariat of Research and Technology (PENED Ontomedia 03 ED 475).