Jun Zheng
email: junzheng@seu.edu.cn

Zhenzhong Huang

Qihuang Shu

Nathalie Mitton

A Distributed Rate Allocation Algorithm for Slepian-Wolf Coding based Data Aggregation in Wireless Sensor Networks

Keywords: distributed rate allocation, Slepian-Wolf coding, data aggregation, wireless sensor network

This paper considers the Slepian-Wolf coding based energy-minimization rate allocation problem in a wireless sensor network (WSN) and propose a distributed rate allocation algorithm to solve the problem. The proposed distributed algorithm is based on an existing centralized rate allocation algorithm which has a high computational complexity. To reduce the computational complexity of the centralized algorithm and make the rate allocation performable in a distributed manner, we make necessary modifications to the centralized algorithm by reducing the number of sets in calculating the average energy consumption cost and limiting the number of conditional nodes that a set can use. Simulation results show that the proposed distributed algorithm can significantly reduce the computational time when compared with the existing centralized algorithm at the cost of the overall energy consumption for data transmission and the total amount of data transmitted in the network.

I. INTRODUCTION

In a wireless sensor network (WSN), a number of sensor nodes are densely deployed in a region of interest to collect data and send the data to the data sink [1] . The data collected by different sensors usually have a certain spatial correlation and the degree of the spatial correlation increases as the distance between sensor nodes decreases [2] . The spatial correlation can lead to considerable data redundancy in the network and transmitting redundant data would cause unnecessary energy consumption. To increase energy efficiency and prolong network lifetime, it is necessary to perform in-network data aggregation to remove the data redundancy in the network.

Slepian-Wolf coding [3] is a distributed source coding technique that can remove data redundancy in a WSN without communication between sensor nodes. When using Slepian -Wolf coding for data aggregation in a WSN, rate allocation is an important issue that has a big impact on the performance of data compression and thus the energy consumption for data transmission in the network [START_REF] Vuran | Spatio-temporal correlation: theory and application for wireless sensor network[END_REF][START_REF] Cristescu | Networked Slepian-Wolf: theory, algorithms, and scaling laws[END_REF]. To reduce the energy consumption for data transmission, it is desirable to find an optimal rate allocation that can maximize data compression and thus minimize the amount of data transmitted in the network, which is referred to as the Slepian-Wolf coding based energy-minimization rate allocation problem. To solve this problem, Liu et al. has proposed a centralized rate allocation algorithm [START_REF] Liu | Power efficient rate allocation for Slepian-Wolf coding over wireless sensor networks[END_REF], which, however, requires a high computational complexity and is thus not practical for being applied to a large network. To address this limitation, it is interesting to explore a distributed rate allocation algorithm to solve the problem, which is the motivation for this work.

In this paper, we consider the Slepian-Wolf coding based energy-minimization rate allocation problem in a WSN, and propose a distributed rate allocation algorithm to solve the problem. The proposed distributed algorithm is based on the centralized rate allocation algorithm proposed in [START_REF] Liu | Power efficient rate allocation for Slepian-Wolf coding over wireless sensor networks[END_REF]. To reduce the computational complexity of the centralized algorithm and make the rate allocation performable in a distributed manner, we make necessary modifications to the centralized algorithm by reducing the number of sets in calculating the average energy consumption cost and limiting the number of conditional nodes that a set can use. Simulation results show that the proposed distributed algorithm can significantly reduce the computational time as compared with the existing centralized algorithm at the cost of the overall energy consumption for data transmission and the total amount of data transmitted in the network.

The rest of the paper is organized as follow. Section II introduces the concept of Slepian-Wolf coding and describes the Slepian-Wolf coding based energy-minimization rate allocation problem considered in this paper. Section III presents the proposed distributed rate allocation algorithm for solving the rate allocation problem. Section IV evaluates the performance of the proposed distributed algorithm through simulation results. Section V concludes this paper.

II. SLEPIAN-WOLF CODING AND PROBLEM STATEMENT

This section introduces the concept of Slepian-Wolf coding and describes the problem considered in this paper.

Slepian-Wolf Coding

Consider a WSN network with one sink and N sensor nodes that are uniformly distributed in a region of interest, where each node k produces reading X k . All the readings produced by the sensor nodes constitute a set of jointly stationary ergodic sources, which is denoted by ( )

N 2 1 X , , X , X … = X
. Assume that the distribution of ( )

N 2 1 X , , X , X … = X is ) ( N 2 1 x , , x , x p …
, which corresponds to the spatial correlation structure known by each node a priori. According to the Slepian-Wolf Theorem [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF], the sensor nodes can jointly encode their data without communicating with each other, with a coding rate (in bits) lower-bounded by their joint entropy ) (

N 2 1 X , , X , X H
… as long as their respective coding rates are under the constraints given by )

) ( ) ( ( ) ( c / H R Φ Φ ≥ Φ X X for all N} , {1,2, = Ω ⊆ Φ
, where

∑ Φ ∈ = Φ k k R R ) ( , } { ) ( Φ ∈ = Φ k , X k X , } { ) ( c Φ ∉ = Φ k , X k X .
For example, for a simple network with two sensor nodes producing readings 1 X and 2 X , their individual coding rates should be subject to

) / ( 2 1 1 X X H R ≥ , ) / ( 1 2 2 X X H R ≥ , ) , ( 2 1 2 1 X X H R R ≥ +
. According to Chain Theory [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF], under the above constraints, there always exists a rate allocation for the two nodes, which makes the total coding rate (bits) of the two nodes equal to their joint entropy, i.e., ) , ( ) / ( ) (

2 1 1 2 1 2 1 X X H X X H X H R R = + = +
. Accordingly, for any order of N nodes, there always exists a rate allocation (vector)

N 1 } { = k k R
that makes the number of bits generated by all the nodes equal to their joint entropy, i.e.,

) ( N 2 1 N 1 X , , X , X H R k k = ∑ = , where ) ( 1 1 X H R = and ) X , , X , X / X ( H R k k k k 1 2 1 - - = .

Problem Statement

Consider the same network described in Section 2.1. For the data produced by each sensor node, i.e., ( )

N 2 1 X , , X , X … = X
, Slepian-Wolf coding is used to jointly encode the data. The encoded data at each sensor node are then transmitted to the sink node along the shortest path between the sensor node and the sink, and are jointly decoded at the sink. Assume that the coding rate allocated for each sensor node is R 1 , R 2 , …, R N , respectively. According to the Slepian-Wolf theorem, the data can be jointly decoded without loss at the sink subject to the following constraint:

)

) ( ) ( ( ) ( c / H R Φ Φ ≥ Φ X X (1) for N} , {1,2, = Ω ⊆ Φ
, where

∑ Φ ∈ = Φ k k R R ) ( , } k , X { ) ( k Φ ∈ = Φ X , } { ) ( c Φ ∉ = Φ k , X k X .
Under the above assumptions, the problem we consider is to find an optimal rate allocation for each sensor node to minimize the amount of data transmitted in the network and thus the overall energy consumption for data transmission subject to the constraint given in Eq. ( 1).

To further describe the above problem, we assume that the path cost for node k to send its encoded data to the sink along the shortest path is w k . The coding rate allocated to node k is R k . Thus, the energy consumption for node k to transmitting the encoded data with rate

R k is ) ( ) ( k k k R c w R E × = , (2) where )
(⋅ c is a function only related to the amount of data or the coding rate. In this paper, we assume that ) exp( ) (

k k R R c = .
(3) Under the above assumptions, the overall energy consumption for transmitting the encoded data to the sink in the network is

∑ ∑ = = × = = N 1 N 1 ) exp( ) ( k k k k k R w R E E . (4)
Therefore, the problem is to find a rate allocation ( )

* N * 2 * 1 R , , R , R * … = R
for each sensor node so that the overall energy consumption for data transmission in the network is minimized

, i.e., ] ) exp( arg[min ) ( N 1 * N 1 ∑ = × = = k k k * * R w R , , R R , ( 5
) subject to )) ( ) ( ( ) ( c | H R Φ Φ ≥ Φ X X .

Centralized Rate Allocation Algorithm

To solve the above problem, Liu et al. have proposed a centralized rate allocation algorithm in [START_REF] Liu | Power efficient rate allocation for Slepian-Wolf coding over wireless sensor networks[END_REF], which is based on the water-filling algorithm and gives an optimal solution to the problem.

In this algorithm, all sensor nodes in the network are divided into two node sets: conditional node set 1 Φ , which is null initially, and non-conditional node set 2 Φ , where

1 2 Φ Ω = Φ / .
In each round, it selects a non-null subset that meets a given condition from all the subsets of 2 Φ , adds all the nodes in the selected subset into the conditional set 1 Φ , and then removes these nodes from the non-conditional set 2 Φ . This procedure is repeated until the non-conditional node set 2 Φ becomes null.

The main procedure of the centralized rate allocation algorithm is described as follows:

1) Let N = n , φ = Φ 1
, where n is the number of nodes in

1 Φ Ω / ; 2) Calculate the value of )) ( ) ( ( 1 Φ Φ X X | H
, where Φ is any subset of set

| | / w | H j j / Φ + Φ Φ = Φ ∑ Φ ∈ Φ ∈ Φ X X Ω ; (6) 4) For each node k in set 0 Φ , set the rate k R , i.e., k j j k w | | / } w | H R ln ln )) ( ) ( ( { 0 1 0 0 - Φ + Φ Φ = ∑ Φ ∈ X X ; (7) 5) Update | | n n 0 Φ - = , 0 1 1 Φ Φ = Φ ∪ ; If 0 = n
, stop; otherwise, go to step 2).

The above algorithm is a global rate allocation algorithm which gives an optimal solution to the problem in Eq. ( 5). However, it has two weaknesses: (a) Step 2) introduces a high computational complexity; (b) Step 3) requires a global comparison of all the values obtained in step 2).

Due to the above two weaknesses, the algorithm has a high computational complexity and thus can only be performed in a centralized manner.

III. DISTRIBUTED RATE ALLOCATION ALGORITHM

In this section, we present our proposed distributed rate allocation algorithm for Slepian-Wolf coding based data aggregation in WSNs. We first make necessary modifications to address the two weaknesses of the centralized algorithm and then describe the procedure of the proposed distributed algorithm.

Reduction of Computational Complexity

For the centralized rate allocation algorithm, it needs to calculate the average energy consumption cost value for any possible subset Φ of set

1 Φ Ω / , i.e., | | / w | H j j Φ + Φ Φ ∑ Φ ∈ } ln )) ( ) ( ( { 1 X X . ( 8
)
Since the number of nodes in

1 Φ Ω /
is n, the number of

possible s Φ is ) 1 2 ( - n
. This means that the computational time of the algorithm increases exponentially with the number of nodes in the network. Obviously, when n becomes large, it is difficult for a sensor node to undertake the huge amount of computation because of the limitation in its computational capability.

To reduce the computational complexity, it is necessary to reduce the number of s Φ that need to be calculated in step 2).

By observing step 3), it is found that the purpose of step 2) is to find the set 0 Φ with the minimum average energy consumption cost value. Thus, we only need to calculate those s Φ that lead to a smaller value of the average energy consumption cost, and ignore other s Φ . In this way, the amount of computational time can be largely reduced. However, this should not significantly degrade the performance of the algorithm. That is, the algorithm should still be able to find the set 0 Φ with the minimum average energy consumption cost value. Therefore, the next question is "What s Φ should be selected for calculation in step 2)?"

As mentioned earlier, Eq. ( 8) represents the average energy consumption cost of set Φ , which consists of two parts: the first part is the average conditional entropy of set Φ and the second part is proportional to the average path cost of set Φ . In general, the data correlation degree between different nodes decreases with the increase of the distance between the nodes. For this reason, the average entropy value of a set whose nodes are away from each other is usually larger than that of a set whose nodes are closer to each other. Based on this fact, it is unnecessary to calculate the cost values of those sets whose nodes are away from each other in step 2). In another word, we only need to calculate those subsets whose nodes are closer to each other. The specific definition of those subsets that need to be calculated will be given in the next subsection.

Distributed Implementation of Rate Allocation

As explained in Section 2.3, the centralized algorithm has two weaknesses that make it only feasible to be performed in a centralized manner: (a) Step 2) needs to calculate the conditional entropy

)) ( ) ( ( 1 Φ Φ X X | H of any possible subset Φ of set 1 Φ Ω /
in step 2). For each subset Φ , it must know the information on all conditional nodes, which is usually globally distributed and thus makes the calculation infeasible to be performed in a distributed manner. (b) Step 3) needs to compare all the conditional entropy values obtained in step 2), which is a global comparison and thus can be only performed in a centralized manner.

To make the algorithm implementable in a distributed manner, the above two weaknesses must be addressed.

A) Limitation of Conditional Nodes

As discussed earlier, to make the computational process of the centralized algorithm implementable in a distributed manner, it is necessary to impose some limitation on the conditional nodes that a set Φ can use. Specifically, we can limit the conditional nodes a set can use to only its local nodes. That is, the conditional nodes of a particular node must be one-hop neighbor nodes of that node. In addition to this limitation, a conditional node must also meet another condition, i.e., it must be a conditional node selected in the last round of calculation (or in set 1 Φ ) like the centralized algorithm.

Next we discuss how to determine the conditional nodes that a set Φ can use. The notations used in the discussion are defined as follows.

' k P : a set consisting of all one-hop neighbor nodes of node k; and consists of only those nodes closer to set Φ . For simplicity, we only consider those "closer" nodes as conditional nodes. Specifically, for a particular set Φ , a node in its conditional node set ' 1 Φ must meet the following condition: a one-hop neighbor node of a node in set Φ . Of course, we can consider a larger range (e.g., two hops) for selecting the conditional nodes. Obviously, the larger the range, the more conditional nodes for a particular node, and the less the performance degrades.

Based on the above definition on conditional nodes, we now discuss how to determine the conditional node set

' 1 Φ for set Φ .
For a particular node k, its conditional node must meet the conditions below:

1) The node belongs to 1 Φ ;

2) The node is one-hop away from node k.

In this case, for set ' k P , its conditional node set is

} { 1 1 ' k i k ' k P k , i ∈ Φ = Φ
. According to the definition of set k P , we can obtain

' k ' k k / P 1 P Φ =
. Based on the above analysis, for a particular node k, we only need to calculate the average energy consumption cost value of a set that consists of node k and any number of its one-hop neighbor nodes, and the nodes in that set cannot be a conditional node in set 1 Φ . Therefore, k P and its real subsets constitute all sets that need to be calculated for node k. In this case, the number of sets that need to be calculated becomes

∑ = n 1 | | 2 j k P . Obviously, we have 1 2 2 n n 1 - << ∑ = j | | k P
when n is large. As a result, the computational complexity of the distributed algorithm is largely reduced.

B) Reduction of Comparison Scope

Next let us consider the global comparison problem in step 3). To make the comparison performable in a distributed manner, it is necessary to reduce the comparison scope in step 3).

As explained earlier, the purpose of the global comparison in step 3) is to find a set with the minimum average energy consumption cost among all possible sets. For this purpose, we can further divide the global comparison into two steps.

(1) For each node k, compare the average energy consumption cost values of all sets that have node k as the center and find the set with the minimum value, which is called representative set of node k.

(2) For each node, compare the average energy cost value of its representative set and find the one with the minimum value.

Since step ( 2) is a global comparison, it is necessary to reduce the comparison scope in this step. By careful observation, we can find the following two facts:

(1) For a particular node v, only when the set consisting of the nodes within the two hops of node v is selected in the current round will the average energy consumption cost value of the representative set of node v change or need to be recalculated in the next round of calculation. (2) For a particular node v, if the average energy consumption cost of its representative set is smaller than that of the representative set of any of its neighbor nodes within two hops, its representative set is selected and added to the conditional node set earlier than the representative set of any of its neighbor nodes within two hops.

Based on the above facts, we can obtain the following conclusion: for a particular node v, we only need to consider the neighbor nodes within its two hops, and can ignore those nodes that are not within its two hops. Therefore, in the distributed algorithm, for those sets that have a particular node v as their center node (i.e., all the other nodes in a set are one-hop neighbor nodes of node v), a set that needs to be compared with these sets must meet the following conditions: 1) The set has a particular node u as its center node and the other nodes in the set are one-hop away from node u; 2) The center node, node u, is at most two hops away from node v.

As a result, the global comparison in the centralized algorithm can be replaced by the local within a two-hop range of a particular node, which makes it feasible to perform rate allocation in a distributed manner. It should be noted that since the algorithm is performed in a distributed manner, in each round of calculation, more than one set may be selected, which is a difference compared with the centralized algorithm.

Distributed Rate Allocation Algorithm

After making the modifications to the centralized algorithm, we now present the proposed distributed rate allocation algorithm and describe its major procedure as follows:

1) Let N = n , φ = Φ 1
, where n is the number of nodes in In the above algorithm, each step only needs local information, which makes it feasible for the algorithm to be performed in a distributed manner and significantly reduces the computational complexity of the algorithm.

IV. SLIMULATION RESULTS

In this section, we evaluate the performance of the proposed distributed rate allocation algorithm through simulation results. For evaluation, we compare the distributed algorithm with the centralized rate allocation algorithm in terms of the overall energy cost for data transmission, total amount of data transmitted in the network, and total amount of computational time.

Given that the centralized algorithm has a high computational complexity, it is inappropriate to consider a network with a large number of nodes in the simulation experiments. For this reason, we considered a 100m×100m area with 100 nodes uniformly distributed. We used the energy model in [START_REF] Heinzelman | An application-specific protocol architecture for wireless microsensor network[END_REF]. and the correlation model in [START_REF] Pattem | The impact of spatial correlation on routing with compression in wireless sensor networks[END_REF]. We assumed that the amount of data generated by one node without compression is 1 bit. The path used for data transmission is the shortest path tree, and the path cost k w of node k is 2 k d , where k d is the path distance between node k and the sink.

Fig. 1 and Fig. 2 show the overall energy consumption and the total amount of data transmitted in the network with the centralized algorithm and the distributed algorithm, respectively. It is seen that the performance of the distributed algorithm degrades as compared with that of the centralized algorithm. This is because in the distributed algorithm the conditional information a particular node can use is limited to only local information. In this case, the conditional entropy value of the node will increase. Since the coding rate of a node is equal to the conditional entropy of the node, the coding rate (or the amount of data) would also increase, which results in the increase of the overall energy consumption for data transmission in the network. On the other hand, the value of the performance degradation depends on the data correlation degree between different nodes. The larger the data correlation degree, the larger the performance degrades. This is because in the distributed algorithm we only consider the nodes within one hop of a node, which would result in less conditional information that can be used by a node.

Fig. 3 shows the computational time in terms of simulation time with the centralized algorithm and the distributed algorithm, respectively. It is seen that the distributed algorithm significantly reduces the computational time as compared with the centralized algorithm.

V. CONCLUTIONS

In this paper, we considered the Slepian-Wolf coding based energy-minimization rate allocation problem in a WSN and proposed a distributed rate allocation algorithm to solve the problem. The proposed distributed algorithm is based on the existing centralized algorithm proposed in [START_REF] Liu | Power efficient rate allocation for Slepian-Wolf coding over wireless sensor networks[END_REF], which has a high computational complexity. To reduce the computational complexity and make the rate allocation performable in a distributed manner, we make necessary modifications to the centralized algorithm by reducing the number of sets in calculating the average energy consumption cost and limiting the number of conditional nodes that a set can use. The simulation results show that the proposed distributed algorithm can significantly reduce the computational time as compared with the existing centralized algorithm at the cost of the overall energy consumption for data transmission and the total amount of data transmitted in the network.

  This work was supported by the National Natural Science Foundation of China under Grant No. 61071115, the Research Fund for the Doctoral Program of Higher Education of China under Grant No. 20110092110007, and the Research Fund of National Mobile Communications Research Laboratory, Southeast University, China, under Grant No. 2012A02.

1 Φ:

 1 The conditional node set of the network. The conditional node set of a particular set Φ is a subset of 1 Φ ;) (⋅ I : the entropy of the mutual information between different nodes.

Fig. 1

 1 Fig.1 Overall energy cost in the network.

Fig. 2

 2 Fig.2 Total amount of data transmitted in the network.

Fig. 3

 3 Fig.3 Simulation time.

We know that the entropy value of mutual information between two nodes has a negative correlation to the distance between the two nodes, and we have

where ' 1 Φ denotes the set consisting of the conditional nodes which are closer to set Φ " Φ denotes the set consisting of the conditional nodes which are away from set Φ , ) ( ⋅ I denotes the entropy of the mutual information between different nodes.

According to the relevant properties of mutual information, the value of

, and thus can be neglected. Similarly, we have

. According to Eq. (9) -Eq. ( 11), we have

Therefore


Valérie Ficet-Cauchard

Christine Porquet
email: christine.porquet@greyc.ismra.fr

Marinette Revenu
email: marinette.revenu@greyc.ismra.fr

An Interactive Case-Based Reasoning System for the Development of Image Processing Applications

In this paper, an interactive system for the development of Image Processing applications is described. This system is intended to provide some assistance to Image Processing experts during the construction as well as the execution of their applications. Through the system's graphical interface, an application can gradually be built and represented as a tree of tasks, and strategies can be made explicit so as to become reusable in future applications. In order to increase the assistance provided by the system, developers must be in a position to reuse parts of pre-existing treatments. To implement reusability, a Case-Based Reasoning approach is used. After defining two sets of criteria related to the task's description and the context of images, that enable us to classify a task in order to know when and how to reuse it, we describe our similarity functions and propose a search / adaptation algorithm for the retrieval of appropriate cases.

Introduction

In Image Processing (IP), the tuning of an application is a complex activity : difficulties arise when it comes to precisely defining a request, working out a solution and evaluating results. To overcome such difficulties, the IP expert has to make the most of the know-how acquired when developing previous applications. But the multiplicity of IP problems and domains of application, as well as the selectivity of human memory do not always allow the IP expert to reuse prior knowledge. Case-Based Reasoning (CBR) provides some kind of answer to the selective memory issue by increasing the IP expert's memory and by helping him to select previously solved cases that are close to his current problem.

In section 2, the distinctive features of IP and their implications on our problemsolving model are presented. Then, our system which enables, on the one hand, knowledge acquisition in Image Processing (IP) and on the other hand, the reuse of this knowledge is described. The acquisition step is done thanks to an interactive system (TMT) (section 3) that allows users to create and execute IP applications, while representing the reasoning brought into play in these applications. The reuse step is managed by a Case-Based Reasoning module (section 4) that provides assistance to users so as to let them build new applications by reusing, as much as possible, previously developed ones.

Problem solving in Image Processing

Distinctive features of IP

In IP, the domain expert plays an important part during the development of applications. First, he / she has to define the problem (by providing one or several images associated with a request) that the IP expert will try to solve. Then, once a solution is proposed, it must be assessed by the domain expert, by viewing the resultant images. In fact, IP is a domain where no ideal evaluation function exists and no one but the domain expert can perform the final validation of an application. This validation can either be done visually, or be based on a more global testing protocol (e.g. statistics on object features extracted from the image). The roles of the domain expert and the IP expert are inter-dependent, thus requiring strong co-operation and communication between experts.

Moreover, the multiple and shaky nature of solutions makes the tuning of applications harder. Actually, any given problem has several solutions that can be more or less adapted to the current image and are more or less sensitive to the noise type and noise level of this image. To tackle these issues, a priori knowledge about expected results must be introduced and various strategies must be tried and tested. A priori knowledge consists of data about the image domain (e.g. in cytology, « cell nuclei are convex ») or data that comes from a thorough scene examination (e.g. « cell nuclei are dark objects laying on a light background »).

The use of operator libraries

The kind of approach we are advocating for the development of IP applications is based on the « intelligent » management of elementary programs stored in libraries, that are called IP operators in our context. Following this approach, building an IP application consists in chaining and tuning a set of operators selected from a given library.

Program libraries are not only used in IP. For instance, several systems developed thanks to the SCARP environment [START_REF] Willamowski | Modélisation de tâches pour la résolution de problèmes en coopération système /utilisateur[END_REF] solve problems by creating sequences of elementary programs stored into libraries (e.g. the Myosis system for electromyography diagnosis, or the Said system for diagnosis of vibrations in offshore oil drill platforms).

Among the IP systems based on such libraries, a distinction should be made between graphical programming environments [START_REF]IRIS Explorer User's Guide[END_REF] [START_REF] Rasure | The Khoros Application Development Environment, Experimental Environments for Computer Vision and Image Processing[END_REF], which enable users to select and organise operators into sequences (but not to justify or represent their reasoning) and automatic planning modules [6] [5] that are based on an explicit knowledge representation enabling reuse (but hardly -or not at all -allow users to intervene during the search for a solution). In order to take advantage of the interactive nature of graphical programming environments, our system should enable users to graphically select and link IP operators. But it should also give them a means to represent and make explicit the reasoning that has led them to this series of operators, with a view towards reusing the implemented strategy, in the same way as automatic systems do.

Our system uses IP operators from the PANDORE library [START_REF] Clouard | PANDORE : une bibliothèque et un environnement de programmation d'opérateurs de traitement d'images[END_REF] developed at the GREYC. Any operator from this library is a program performing an operation that cannot be further decomposed. Thus, any complex operation has to be decomposed into a sequence of several operators. Each operator takes as inputs images and numerical parameters and produces as outputs images and other (non-image) results. It can perform a specific operation on various image formats (pixel image, label image, region map, ...) and inputs / outputs are normalised.

Plan-based representation

An actual application can lead to sequences of up to tens of operators. In order to make explicit the reasoning brought to light during this process, our approach is to represent applications by means of IP plans. An IP plan is built by hierarchical decomposition of an original problem into simpler sub-problems. Each problem or sub-problem is associated with an IP task which, according to its level within the plan, will either describe the goal to be reached, the technique to be used or the algorithm to be applied. Such an approach based on the use of generic and decomposable tasks is widespread in problem solving [START_REF] Benjamins | Assumption of Problem-Solving Methods[END_REF] [START_REF] Chandrasekaran | The Ontology of Tasks and Methods[END_REF].

A plan can be schematised as a tree (fig. 1) which not only represents the linking and execution of IP operators corresponding to the leaves of the tree, but also the reasoning that lead to the building of such sequences of operators; this reasoning is represented by means of IP tasks schematised as grey rectangles.

Fig. 1. plan representation

Reusability of applications

When IP experts are building applications in various domains, and representing them as IP plans, they should be able to reuse previously built parts of plans. They can actually be faced with a problem that was previously solved in other applications. For instance, the search for a particular type of cell nucleus in a cytological image (fig. 2 But one should also wish to solve a new problem dealing with a kind of image that has already been treated, or close to it. For instance, cytological and histological images of fig. 2, are somewhat analogous in the sense that they are both coming from the same biomedical material and the same acquisition device (microscope). The associated requests are however completely different : cell classification in the former versus extraction of clusters of cells in the latter (fig. 2-c and2-f). But it turns out that the first two IP steps are identical (noise elimination and background elimination). When building the second plan, one should thus try to reuse these two steps of the first plan. To implement this kind of reuse, our approach is based on CBR techniques. CBR solves a new problem by retrieving and adapting solutions or parts of solutions of a previously solved problem. It is based on a kind of reasoning that is close to human reasoning, and is thus well-suited for man/machine co-operation and enables us to focus on several categories of data about the plan, i.e. data about the request, the input images or the strategy to carry out.

Knowledge acquisition and modelling

The TMT model

In our system, three knowledge levels are defined : the domain level (Image Processing) and the control and metacontrol levels that manage the representation and use of domain knowledge.

Domain knowledge includes knowledge about the application (to describe a priori information about image domain or expected results), knowledge about IP (to find out which strategies to carry out) and knowledge about operators (to select them, tune their parameters or form syntactically correct sequences of operators, ...).

Control knowledge is in charge of managing domain knowledge (plan creation, plan execution, method selection, ...) and controlling the system's behaviour (visualisation of the operations to perform, selection of the treatments accessible to users, supervision of sequences of operators, ...).

Metacontrol knowledge is knowledge about how to control the system's control and defines the system's behavioural rules with regards to users.

In our system, all three levels are uniformly represented thanks to the « TASK- METHOD-TOOL » (TMT) architecture [START_REF] Ficet | Construction interactive d'un modèle conceptuel d'applications de traitement d'images[END_REF].

A TASK represents a goal or sub-goal and contains all elements that are necessary to satisfy this goal (type of data, type of result, solving methods, ...). When a task solves a general-purpose problem, it is defined as a decomposition of sub-tasks that solve more elementary problems, and each sub-task can further be decomposed into simpler ones. When a task can be performed in several ways, it is associated with several methods (fig. 3-a).

A method specifies how to perform a task. Each method is associated with a single task, but a task can be solved by several methods. So one has to tell, for each method, when it could be used. The method body can take two forms : either a decomposition into sub-tasks (fig. 3-c), described as a « THEN » tree -this is called a complex method, or the call to a run-time program through the medium of a tool (fig. 3-b) -this is called a terminal method. The set of sub-tasks that will be executed to perform a given task depends on the selected method ; so it is methods that manage task / subtask and task / tool data flows. A tool reifies a computer code, which means it is a user-oriented representation of this code in conceptual terms (goal, inputs, parameters, outputs, syntax of call, performances, resources, ...) with a link to this code enabling to run it. From a user's point of view, this code can be seen as a black box : all that is known about it is the nature of transforms performed on inputs to produce outputs and the only possible action is the tuning of parameters. At the domain level, tools mainly reify basic IP operators of the PANDORE library (e.g. image thresholding, image smoothing, ...), but they can reify external Lisp or C functions likewise.

Interactive building of IP plans

Our knowledge-based system is provided with a graphical interface favouring man / machine co-operation for plan creation and execution. When wishing to tune a new application, users can build their tasks and tools by filling in fields in adapted windows. Then, tasks and tools are linked by the means of methods. The task associated with a method is selected in a menu, as well as its associated sub-tasks or tool. All components are automatically stored in files and data flows are defined in a user-friendly way by drawing lines between elements on a diagrammatic figure of the current plan. As it is possible to define all components in any order, users can adopt either a bottom-up building process (grouping sub-tasks together), or a top-down one (decomposing into sub-tasks), or even a mixed one.

To perform some processing on an image, users have to select a task in a menu; the corresponding plan is then instantiated when the image is given as input to the plan. The task is executed by proposing a choice of existing methods, when several methods exist to solve one task, and asking for parameter values if necessary. During execution, users can visualise intermediate images that are input or output of any task of the plan, or have access to data about tasks and solving methods, through the graphical figure of the plan as a tree of tasks.

Providing assistance to reuse

Owing to its closeness to human reasoning [START_REF] Kolodner | Improving Human Decision Making through Case-Based Decision Aiding[END_REF], Case-Based reasoning provides an attractive means to implement the reuse of IP plans, for it leads to a natural form of man / machine co-operation. When this kind of reasoning is used for planning purposes, it is called Case-Based planning, and finds applications in various domains such as building synthesis plans in organic chemistry with ReSYN/RàPC [START_REF] Lieber | Planification à partir de cas et classification[END_REF], providing assistance to automatic program synthesis with Déjà-Vu [START_REF] Smyth | Retrieval & Adaptation in Déjà-Vu, a Case-Based Reasoning System for Software Design[END_REF], or process planning with CAPLAN/CBC [START_REF] Veloso | Case-based planning : selected methods and system[END_REF].

Case representation

In Case-Based planning, the representation of cases and the representation of plans must be closely related. In a system such as ReSYN/RàPC, where a plan corresponds to an ordered sequence of steps (a step being a state plus a transition), a case can be represented as a triplet < set of steps , initial state , final state >. This kind of representation is convenient when plans are not composed of too large a number of steps, or when the adaptation phase can be fully automated, which is not feasible in IP. So as to build a solution by combining plans, one has to resort, as in Déjà-Vu, to a representation enabling access to a plan at various abstraction levels. In our system, a case is defined as a pair < IP problem, TMT plan solution to this problem >. The solution plan can be accessed through its root task, with which are associated a set of criteria characterising this task and the problem it solves. These criteria are classified along two axes, whether they are dealing with the task's description or the application's context.

Criteria related to the task's description

These criteria are composed of the processing type or the processing step, the actual definition of the problem and the associated task's abstraction level.

According to the abstraction level of the current problem, either the processing type (image segmentation, image restoration, ...) or the processing step (e.g. in the case of segmentation : pre-processing, finding out of seeds, boundary localisation, ...) can be taken into account.

The problem definition is made up of a set of keywords that can be selected from keywords indexed in three lists : a list of verbs (the operations to perform, e.g. detect, classify, binarise, ...), a list of nouns (the objects on which the operation is performed, e.g. boundaries, regions, labels, ...) and a list of adjectives (to qualify the operation or the object, e.g. local, large, partial, ...).

Finally, abstraction levels, which correspond to a horizontal division of the plan, are based on those defined in the automatic planner BORG [START_REF] Clouard | A software Workbench for Knowledge Acquisition and Integration in Image Processing[END_REF] and are also closely related to the three abstraction levels mentioned by David Marr [START_REF] Marr | Vision : A computational investigation into the human representation and processing of visual information[END_REF] in his study about visual perception. The first abstraction level is the intentional level. Tasks at this level answer the « what to do ? » question and deal with IP objectives. The second level is called the functional level. Tasks at this level answer the « how to do ? » question and represent IP techniques, leaving aside technical constraints related to implementation. The third and last level is the operational level. Tasks at this level answer the « by means of what ? » question and represent a technical know-how in IP that can be implemented as algorithms. This level is close to the notion of IP operator, but without being linked to any specific library of operators.

Criteria related to the context of images

Among the criteria related to images, some of them describe image quality. In particular, they are dealing with noise type, noise amount, contrast quality. Such criteria are particularly important when it comes to choosing preliminary processing steps (noise reduction, contrast enhancement, …).

Other criteria are somewhat related to semantic image description and the kind of objects that are to be extracted. One can mention the presence or absence of image background, the aspect of the objects to be detected (homogeneous grey level, light colour, textured region, thick boundaries, ...), their form (convex, concave, elongated, compact, ...), their relative size and relative position (right, left, under, above, at the centre of, ...) compared to the other objects of the scene and finally, inter-object relations (near, connected, included, ...).

Similarity calculation

Two kinds of approaches can be considered for the retrieval of similar cases, whether they are based on maximising similarity [START_REF] Caulier | Apport de la modélisation des connaissances à partir de cas pour la capitalisation et la réutilisation de connaissances[END_REF], or minimising adaptation effort [START_REF] Smyth | Retrieval & Adaptation in Déjà-Vu, a Case-Based Reasoning System for Software Design[END_REF] [START_REF] Munoz-Avila | Feature Weighting by Explaining Case-Based Problem Solving Episodes[END_REF]. In IP, as there is no suitable automatic evaluation method, only the second approach is conceivable. Moreover, all the previously mentioned criteria are not taken into account in every application. So, like ISAC [START_REF] Bonzano | ISAC : A CBR System for Decision Support in Air Traffic Control[END_REF], we need an iterative process in order to determine which are the important criteria for the current case. This process takes place in co-operation with the user that has to provide data to fill in criteria or to order them according to their importance with regards to the current case.

The order on criteria enables us to assign them an importance coefficient Cr α , nonfilled criteria being affected with a null value. Comparison functions ( ) T S Cr , ϕ are defined to compute similarity between a source case S and a target case T on each criterion Cr. These functions return a value between 0 and 1 and are defined according to the criterion type : proportion of common items for criteria defined as a list of terms, such as the problem definition ; distance calculation for numerical criteria, such as noise level, contrast quality, and abstraction levels. Comparison functions and importance coefficients are used in two similarity functions, ( )

T S t , Φ and
( )

T S i , Φ
, that are normalised by the sum of coefficients :

( ) ( ) ( ) { } n descriptio s task' the to related criteria , , ∈ ∀ × = Φ ∑ ∑ Cr T S T S Cr Cr Cr t α ϕ α
The use of these functions is described in the next paragraph. Take note that some criteria are directly filled in by the user, whereas others are either computed (e.g. contrast) or deduced from the image domain (e.g. noise).

Case retrieval of previous solutions

Some CBP systems base their search for a solution on the selection of strategies for the decomposition of a problem into sub-problems. Déjà-Vu, for instance, operates in several cycles : at each cycle, a search for a sub-solution to one of the sub-problems is done, this sub-solution being either a concrete solution or, in turn, a decomposition into sub-problems. We, for our part, like CAPLAN/CBC, are rather aiming at first selecting a whole plan, the description of which is close to the current problem, then adapting it by re-using parts of other plans.

In most systems, the selection of the nearest case from the current case is done in several steps : search for compatible cases, search for the more adaptable ones, then user consultation to validate the final choice in ISAC; prototype selection to reduce the search space, then selection of the case that best satisfies the problem in EADOCS [START_REF] Netten | Case Combination for Conceptual Design[END_REF]. As for us, we also operate in several steps, aiming first at reducing the search space by means of function t Φ , then at selecting the nearest cases to the current case thanks to function i Φ , and at last consulting the user for the final decision.

As was explained in the previous paragraph, the retrieval of a suitable case consists in finding out the root task of the associated plan. This search is done according to the following search/adaptation algorithm :

1-ask user for values of criteria related to the problem's description 2-determine the set T of the tasks matching the desired criteria by means of iterative nature of step 3 enables us to ask for criteria values until a small enough list of cases is reached, in which the user can make his/her choice, while taking into account the importance order of criteria (the earlier a criterion is filled in, the higher its importance coefficient). This also allows us to only fill in the indispensable criteria, so as to leave enough weight to the intuitive aspect that characterises the user's final choice.

Adapting the case to the current problem

In CBP, plan adaptation can either be done through generation or transformation. Adaptation by generation is based on a planner-generator in order to solve remaining goals, as in CAPLAN/CBC, or to refine an abstract solution, as in PARIS [START_REF] Veloso | Case-based planning : selected methods and system[END_REF]. Adaptation by transformation proceeds by substitution or instantiation of sub-solutions taken from other cases, as in EADOCS.

In our system, plan adaptation consists of modifying some sub-tasks or some tools. These modifications can be local (replacement of an operator by another one or modification of parameter values) or global (replacement of a sub-plan by another one). To achieve such modifications, the search/adaptation algorithm is applied locally and recursively. More precisely, once a task is selected at step 4, the user can modify the associated plan by re-starting the algorithm on unsuitable sub-tasks, or by creating new parts of plans with the help of TMT. This recursive aspect of the algorithm ensures plan adaptation at any level in the tree of tasks. Plan evaluation, as well as final validation allowing integration into the base of cases are done by the user after plan execution and result assessment.

Conclusions

In this paper, a computational system based on the TMT architecture and equipped with a graphical interface for user-friendly man / machine interaction has been described. We have also tried to show how Case-Based Reasoning could increase the assistance provided by our system. For this purpose, a search / adaptation algorithm and selection criteria have been proposed, in order to find out when an IP task is reusable. As it is possible to re-apply this algorithm locally and recursively, users can adapt their plan as accurately as desired. Several plans dedicated to various IP problems and dealing with images from different origins have been labelled by means of the selection criteria described in this paper. The good detection of similarities between these plans thanks to this labelling reinforces our confidence in the relevance of our criteria. The validation of the CBR module is presently being completed by effective implementation and testing of the search / adaptation algorithm.

Fig. 2 .

 2 Fig. 2. input image and output image (or intermediate result) for the following applications : a, d : cell classification in cytological image b, e : sorting industrial components c, f : extraction of clusters of cells in histological image

Fig. 3 .

 3 Fig. 3. Various possible links between TASKS, METHODS and TOOLS


Christine Porquet
email: christine.porquet@greyc.ismra.fr

Régis Clouard

Valérie Ficet

Marinette Revenu

DEVELOPMENT OF IMAGE PROCESSING APPLICATIONS WITHIN A COOPERATIVE KNOWLEDGE-BASED WORKBENCH

Keywords:

Solving an Image Processing problem involves three main categories of experts: experts from the domain of application (biologists, geographers...), Image Processing experts and designer-programmers. Domain experts are requested to express clearly and exhaustively the purpose of their application. Image Processing experts have to propose some kind of answer in terms of Image Processing plans adapted to the specific features of the request and the nature of images. Designer-programmers have to provide a framework for an efficient implementation.

We are interested in setting up a Knowledge-Based workbench directed toward the cooperation between these experts and the system. This approach is motivated by the development of real-size applications, while being concerned in generic principles and knowledge acquisition and integration concerns. It hinges on the supervision of a library of Image Processing operators. Solving a specific application is a planning process which implies selecting the suitable operators, linking them and tuning their parameters. An application is thus represented as an Image Processing plan.

After giving the specifications of our system, which belongs to the more general class of Knowledge-Based systems for program supervision, our software architecture favoring cooperation as well as knowledge integration will be presented. This reflexive architecture is based on the TASK/METHOD/TOOL paradigm and provides conceptual models of applications that are actually computational. Several Image Processing plans dealing with biomedical (cytological / histological) images have already been built within our workbench, which constitutes a first convincing validation of our approach.

-Introduction

Image Processing (IP) is a domain where experts of various origins have to cooperate (experts from the domain of application (biology, cartography, geology, ...), IP experts and designer-programmers. Knowledge-Based systems can bring an answer to this cooperation requirement by favoring communication and insuring incremental knowledge acquisition. The objective of our research project of a software workbench for knowledge integration in Image Processing and Image Understanding is to develop such a Knowledge-Based system applied to Image Processing and Image Understanding [Revenu 95]. Our workbench hinges on the supervision of a library of Image Processing operators. Solving a specific application is a planning process which implies selecting the suitable operators, linking them and tuning their parameters. An application is thus represented as an Image Processing plan. We are neither aiming at realizing a general-purpose IP system, nor at only solving dedicated realsize applications, but chiefly at formalizing expert knowledge. First validations are done on biomedical (cytological / histological) images.

The work described in this paper deals with the construction of IP plans thanks to our reflexive architecture based on the TASK/METHOD/TOOL paradigm. After giving the specifications of our workbench ( §. 2), we will detail the various types of knowledge that must be handled and explicitly represented ( §. 3), then the TASK/METHOD/TOOL architecture will be described ( §. 4). The last paragraph will be devoted to the validation of our approach as well as future prospects.

Specifications

Three types of experts play a part in the conception of IP systems and the resolution of IP problems: experts from the domain of application, IP experts and designer-programmers.

First, the domain expert has to define his/her problem by providing one or several images, a request and an application context. Once the corresponding plan is built and in order to test it, the system must then execute it by proposing choices at various levels, as well as possible backtracking from these choices (for instance, choice on methods or on parameters).

The role of the IP expert is to build a plan answering the problem set by the domain expert. Within our workbench, the IP expert no longer has to program in the classical sense of the term, or to have access to computer codes: he/she just has to create plans by organizing predefined basic building blocks.

The designer-programmer is in charge of implementing the control architecture and these basic blocks in order to create the system. Afterwards, the IP expert can appeal to him/her if new operators must be added. These three roles are not independent from each other, which implies cooperation and communication requirements between experts. This communication first consists in making the decomposition of the initial problem into sub problems explicit. In order to favor dialogue between experts and the system, and to cut oneself off as much as possible from technical IP particulars, we propose to program at the knowledge level [Newell 82], i.e. to describe the resolution method by using a vocabulary than can be comprehensible for all experts. A computational conceptual model of the system enables the experts to intervene in the evaluation and tuning of the resolution method [Delouis 93]. Moreover one good means of favoring communication is to develop a graphical interface for visualizing IP plans and intermediate images [Willamowski 94].

Within our workbench, a first work was devoted to the conception of an automatic planning module named BORG [Clouard 95a]. Difficulties in the writing of knowledge sources led us to a more pragmatic approach of step-by-step construction of IP plans. However, our objective is to have our system and BORG cooperate, so as to build a plan, either manually with the help of the IP expert, or automatically by BORG.

The system can appeal to the domain expert or the IP expert when some data are missing, or to make choices between several techniques. But experts can also intervene when they want explanations or in order to modify some choices made by the system. To that purpose, users must be directly involved in the resolution loop, providing they wish to take part in the resolution process and detain the required knowledge. So the system has two functioning modes when executing a plan, automatic mode when the system makes choices, and step-by-step mode when it is the user that makes choices.

Our research takes place within the context of supervision of library of operators [Thonnat 95]. Contrary to systems such as OCAPI [Clément 93] or VSDE [Bodington 95], the objective of which is problem solving, in our system, the manual construction of new applications does not impose writing production rules or knowledge sources. This writing may take place afterwards, or not at all. When executing a plan, if a conflict arises between several methods, and no decision rule is available, a default-choice mechanism will apply. An IP expert can thus create or modify his/her own applications without affecting the other existing applications.

-Knowledge-Based systems in Image Processing

Knowledge-based systems can manage "abstract" data such as the description of the steps to solve some problem [ Wielinga 92]. They bring into play strategic knowledge while authorizing the use of traditional data processing tools and proposing a natural means of interaction with users. Thus, they answer our requirements concerning multiexpert cooperation, knowledge modeling and linking of IP operators. Before building our Knowledge-Based system, the choice of a conceptual model implies a thorough study of the various kinds of knowledge that is needed.

Our system has three knowledge levels: domain knowledge, control knowledge and metacontrol, the first level being decomposed into three categories:

-knowledge about the application, to give a meaning and a subject to an image. This knowledge is mainly given at the beginning of the resolution but can also be provided in case of ambiguity or incompleteness, -IP knowledge to determine the strategies to be used to perform a task and evaluate results, -knowledge on operators to select them, tune their parameters and form syntactically correct sequences of operators.

Control knowledge is knowledge that facilitates the management of domain knowledge. It is dealing with the methodology followed to solve the application and its explicit representation. Two categories can be distinguished:

-domain control dealing with the management of IP plans (creation, modification, execution, ...),

-system control dealing with the visualization of operations, the selection of the treatments accessible to the user, the control of sequences of operations,.... Finally, metacontrol knowledge define the behavioral rules of the system with regards to users. The control must be adapted to the user (one cannot propose the same activities to an expert and a beginner) and his/her wishes (automatic or step-by-step mode, explanations and assistance during a session, ...).

We have chosen to create an interactive environment favoring the incremental development of applications. This environment is the place for the acquisition of new knowledge. Integrating new knowledge in the system is done along two axes: procedural integration to achieve tasks and semantic integration to make them explicit. On the one hand, we want to collect domain and control knowledge (and may be metacontrol knowledge) in an independent but similar way. But we must also account for the fact that an IP request has no unique solution: there generally exist several techniques to satisfy it. It is in this multiplicity of solutions that the integration of ontological and structural knowledge takes all its importance. Thanks to this knowledge, the user will be in a position to decide when a technique should be preferred to the others.

Our study of the problems set by the realization of IP applications, as well as our desire to have the three types of experts cooperate, have led us to choose an architecture answering these requirements: the TASK/METHOD/TOOL architecture.

-Conceptual model: the TASK/METHOD/TOOL architecture

As indicated by its name, the TASK/METHOD/TOOL is based on three notions we are now going to detail.

A task is the representation of a goal or a sub goal in the system. It describes this goal together with information necessary to reach it: input data, type of results, resolution methods. When a task describes a general problem, it is decomposed into sub tasks describing more elementary problems, these sub tasks being in turn decomposable. As a task can be solved in several ways, one or more methods are associated to it.

Tasks can represent all the goals of the system, whatever their level: -domain level: tasks represent an IP objective or some part of it (e.g.: extract clusters of cells or eliminate the background of the image).

-control of the domain level: tasks model operations to be performed on IP plans (e.g.: execute a plan, store a plan). They can either be executed by the system or by the user.

-control of the system level : they regroup tasks controlling the good progress of a work session (e.g.: initialize system, control the interface). Only the system can execute them.

-metacontrol level: tasks represent control on control operations, i.e. metatasks (e.g.: execute a task, choose a method).

Thanks to our uniform model of tasks at all levels, we can say that the triplet {metacontrol, {control, domain}} defines a reflexive system, which provides richness, flexiblity and adaptability to our model.

A method specifies how to perform a task. Each method is associated to a single task but a task can be associated to several methods. (fig. 1-a). When modeling a task, one has to tell when it is possible and desirable to use it. So, although in some contexts, a method can be triggered because all the data necessary to its execution are present, it can be judged irrelevant and unsuited to the current problem. The choice of a method can be done either by the user (step-by-step mode), or by the system (automatic mode).

The body of a method can take two forms: -a decomposition into sub tasks described as an AND/THEN tree, in the case of a complex method (fig. 1 b).

-the call to a run-time program through the medium of a tool in the case of a terminal method (fig. 1-c).

We have defined the concept of tool for reifying computer codes, i.e. in our case mainly IP operators. A tool models a computer code by describing its goal, inputs, parameters, outputs, syntax of call, performances, resources ... For the user, the code associated to a tool can be seen as a black box: he/she only has to know the transformation performed on inputs to produce outputs. Three executing modes are available: normal mode (simple execution of the operator), loop-for mode (execution of the operator a fixed number of times) and optimization mode to dynamically calculate the values of parameters on the basis of measures made directly on images. The latter mode correspond to classical loop constructs (while, until, best-before ...) and uses an evaluation function to check the relevance of the result with regards to desired criteria. We are here inspired by [Matsuyama 89] and [Clément 93]. Our representation of control loops and the fact that the source code is available enables us to generate the C++ program corresponding to a complete plan.

When wishing to perform some processing on an image, the user first has to select the corresponding task in a menu. Secondly, he/she is asked to enter parameters and input data for the plan corresponding to this task. The system can then execute the task by proposing choices among existing methods (in the step-by-step mode) or by selecting by itself the most relevant method according to the context (in the automatic mode). If results are unsatisfactory or even non existing, the system proposes or does itself a backtrack on these choices.

5-Validation of the approach and future prospects

The first prototype of our workbench for manual construction of plans and their execution is implemented in CLOS (Common Lisp Object System). Several Image Processing plans dealing with biomedical (cytological / histological) images provided by the cancer-research center of Caen have already been built and integrated within this environment, which constitutes a first convincing validation of our approach.

In the case of cytological images, we have built manually a plan to solve a task of detection of nuclear cells. This plan was also built automatically by our planning module BORG [Clouard 95a]. We could thus show the compatibility of the two aspects of our workbench: manual versus automatic construction and execution of IP plans.

In the case of histological images, we studied the problem of detection of tumoral clusters of nuclei. The fact that we modeled the analysis methodology as a TASK/METHOD/TOOL plan, rather than just linking operators, brought new ideas into light, so as to improve some sub tasks (e.g.: replacement of a sub task for computing distances of graphs by another more ) and it also gave us a more global view of the whole process.

The ease of coding these plans, and the rapidity of their integration into our environment, are reinforcing our conviction that our approach is promising. While continuing our knowledge acquisition process by integrating new IP plans, we are also studying how to reinforce man/machine cooperation between experts and the system. Recent works about the role of cooperative agents in Knowledge-Based systems [Monclar 96] [Hadj Kacem 96] are particularly interesting.

In order to improve cooperation, a graphical interface (fig. 2) adapted to the various types of users is being developed, including a plan-editor for the visualization and manipulation of the tasks, methods and tools of a plan.

Then, we shall have to imagine how to establish cooperation between the two aspects of our workbench: manual construction and automatic construction of IP plans by BORG, in order to solve more and more complex image processing and image understanding problems.

Figure 1 :

 1 Various possible organizations of tasks, methods and tools (1-a): Several methods can be associated to a task (1-b): Task / sub task decomposition (complex method)(1-c): Method calling a tool (terminal method).