s2fieldsofstudy:
Computer Science
Mathematics

text:
Compilability of Abduction

Abduction is one of the most important forms of reasoning; it has been successfully applied to several practical problems such as diagnosis. In this paper we investigate whether the computational complexity of abduction can be reduced by an appropriate use of preprocessing. This is motivated by the fact that part of the data of the problem (namely, the set of all possible assumptions and the theory relating assumptions and manifestations) are often known before the rest of the problem. In this paper, we show some complexity results about abduction when compilation is allowed.

Introduction
Deduction, induction, and abduction [Pei55] are the three basic reasoning mechanisms. Deduction allows drawing conclusions from known facts using some piece of knowledge, so that "battery is down" allows concluding "car will not start" thanks to the knowledge of the rule "if the battery is down, the car will not start". Induction derives rules from the facts: from the fact that the battery is down and that the car is not starting up, we may conclude the rule relating these two facts. Abduction is the inverse of deduction (to some extent [MF96]): from the fact that the car is not starting up, we conclude that the battery is down. Clearly, this is not the only possible explanation of a car not starting up. Therefore, we may get more than one explanation. This is an important difference between abduction and deduction, making the former, in general, more complex.
While deduction formalizes the process of drawing conclusions, abduction formalizes the diagnostic process, which attempts to invert the cause-effect relation by inferring the causes from its observable effects. The example of the car shows such an application: complete knowledge about car would allow finding (i.e., abducing) the possible reasons of why the car is not starting up. The following example shows how abduction can be applied to formalize a diagnostic scenario.
Example 1 While writing a paper with some authors located in another country, you get a set of macros that are used in a nice figure they drew. However, when compiling the .tex file, an incomprehensible error message results. Four explanations are possible: a : the macro has been used with the wrong arguments; p : the package X is required; t : the macro is incompatible with package X; v : the wrong version of TeX has been used.
This scenario can be formalized in logical terms by introducing a variable f to denote the presence of compile errors: since each of the facts above causes f , we know a → f , p → f , etc. Moreover, we know that a package cannot at the same time be required and incompatible with the macros. The following theory T formalize our knowledge.
This theory relates the observed effect (the compile error) with its possible causes (we used the wrong version of TeX, etc.) Therefore, it can be used to find the possible causes: namely, an explanation is a set of facts that logically imply the observed effect. Formally, an explanation is a set of variable that allow deriving the observed effects from the theory T . However, to make sense an explanation has to be consistent with our knowledge, that is, with the theory T .
This example shows that a given problem of abduction may have one, none, or even many possible solutions (explanations). Moreover, a consistent and an implication checks are required just to verify an explanation. These facts intuitively explain why abduction is to be expected to be harder than deduction. This observation has indeed been confirmed by theoretical results. Selman and Levesque [SL90] and Bylander et al. [BATJ89] proved the first results about fragments of abductive reasoning, Eiter and Gottlob [EG95] presented an extensive analysis, and Eiter and Makino have shown the complexity of computing all abductive explanations [EM02]. All these results proved that abduction is, in general, harder than deduction. The analysis has also shown that several problems are of interest in abduction. Not only the problem of finding an explanation is relevant, but also the problems of checking an explanation, or whether a fact is in all, or some, of the explanations are.
A common fact about deduction and abduction is that the knowledge relating facts may be known in advance, while the particular observation may change from time to time. In the example of the car, the fact that the dead battery makes the car not to start is always known, while the fact that the battery is dead may or may not be true. The possible causes of TeX errors are known before a specific error message comes out, etc.
We can therefore assign two different statuses to the knowledge base and to the single facts: while the knowledge base is fixed, the single facts are varying. In the example above, T will always reflect the state of the word, while f is only true when the TeX complains about something. This difference has computational consequences. While the example we have shown here does not present any problem of efficiency, larger and more complex abduction problems result from the formalization of real-world domains. The difference of status of T and the observations can then be exploited. Indeed, since T is always the same, we can perform a preprocessing step on it alone, even before the status of the observations are known. Clearly, we cannot explain an observation we do not know. However, this preprocessing step can be used to perform some computation that would otherwise be done on T alone. As a result, finding a solution might take less time when the observation finally get known.
The idea of using a preprocessing step for speeding-up the solving of abduction problems is not new. For instance, Console, Portinale, and Duprè [CPT96] have shown how compiled knowledge can be used in the process of abductive diagnosis.
Preprocessing part of the input data has also been used in many other areas of computer science, as there are many problems with a similar fixedvarying part pattern. However, the first formalization of intractability with preprocessing is relatively recent [CDLS02]. In this paper, we characterize the complexity of the problems about abductions from this point of view.

Preliminaries
The problem of abduction is formalized by a knowledge base, a set of observations, and a set of possible facts that can explain the observations. In this paper, we are only concerned about propositional logic. Therefore, the knowledge is formalized by a propositional theory T . We usually denote by M the set of observations.
The theory is T must necessarily contain all variables of M, otherwise there would be no way of explaining the observations. In general, the theory T contains other variables as well, describing facts we do not know whether they are true or not. Some of these facts can be taken as part of a possible explanation, while others are can not. Intuitively, when we are trying to establish the causes of an observation, we want the first cause, and not something that is only a consequence of it. In the example of the car, the fact that there is no voltage in the starting engine explains the fact that the car is not starting up, but it is not an acceptable explanation, as it does not tell where the real problem is (the battery). Therefore, the abduction problem is not defined only in terms of the theory and the observation, but also of the set of possible facts (variable) we would accept as first causes of the observation.
Formally, an instance of abduction is a triple H, M, T . The observations are formalized as M, which is a set of variables. T is a propositional theory formalizing our knowledge of the domain. Finally, H is a set of variables; these variables are the ones formalizing facts that we regards as possible first causes.
Abduction is the process of explaining the observation. Its outcome will therefore be a set of facts from which all observations can be inferred. Since we can only use variables of H to form explanations, these will be subsets H ′ ⊆ H. Moreover, an explanation can only be accepted if it is consistent with our knowledge. This leads to the following definition of the possible solutions (explanations) of a given abduction problem H, M, T .
We apply this definition to the running example of the TeX file.
Example 2 The propositional theory of the example shown in the introduc- All non-empty subsets of H implies, together with T , the observation M. However, the subsets containing both p and t are inconsistent with T . Therefore, the set of solution of the problem is given by: This is simply the formal result of our current definition. However, some explanations in this set are not really reasonable: for example, the explanation is {a, t, v} seems overly pessimistic: the macro has been called in the wrong way and a package is required and we used the wrong compiler version.
The set SOL(H, M, T ) contains all explanations we consider possible. However, some explanations may be more likely than others. For example, explanations requiring a large number of assumptions are often less likely than explanations with less assumptions.
Likeliness of explanations is formalized by an an ordering over the subsets of H. Given a specific , the set of minimal solutions is defined as follows.
SOL The ordering is used to formalize the relative plausibility explanations: H ′ ≺ H ′′ means that H ′ is considered more likely to be the "real" cause of the manifestations than H ′′ . The ordering represents the concept of "at least as likely as", thus H ′ ∼ = H ′′ holds if H ′ and H ′′ are equally likely. The definition of SOL formalizes the principle of choosing only the explanations we consider more likely. An implicit assumption of this definitions is that the ordering does not depend on the set of manifestations. We also assume that is a "wellfounded" ordering, that is, any non-empty set of explanations has at least one -minimal element. Therefore, if the set SOL(H, M, T ) is not empty, then min(SOL(H, M, T ), ) is not empty as well.
In this paper we take into account several plausibility ordering. The absence of a preference among the explanations can be formalized as the ordering that is equal to the universal relation, that is, H ′ H ′′ for any pair of sets of variables H ′ and H ′′ .
Besides this no-information ordering, the two simplest and most natural orderings are ⊆-preference, where an explanation H 1 is more likely of H 2 if H 1 ⊆ H 2 , and ≤-preference, where H 1 is preferred to H 2 if it contains less hypothesis, that is, |H 1 | ≤ |H 2 |.
Both these orderings are based on the principle of making as few hypotheses as possible, and by assuming that all hypotheses are equally likely. Two other orderings follows from assuming that the hypotheses are not equally likely: the ⊆-prioritization and the ≤-prioritization.
In particular, we assume that the hypotheses are partitioned into equivalence classes of equal likeliness. Let H 1 , . . . , H m be such a partition. By definition, it holds H 1 ∪ · · · ∪ H m = H and H i ∩ H j = ∅ for each i = j. The instances of the problem of abduction can thus be written as H 1 , . . . , H m , M, T . The set of all assumptions H is implicitly defined as the union of the classes H i . We assume that the hypotheses in H 1 are the most likely, while those in H m are the least likely.
The ⊆-prioritization and ≤-prioritization compare explanations on the basis of their relative plausibility. Namely, the explanations that use hypothesis in lower classes are more likely than explanations using hypothesis in higher classes. This idea, when combined with subset containment, defines the ⊆-prioritization. When it is combined with the cardinality-based ordering, it defines the ≤-prioritization. Formal definition is below.
Penalization is the last form of preference we consider. The idea is to assign weights to assumptions to formalize their likeliness. Explanations with the least total weight are preferred. Weights encodes the likeliness of assumptions: the most high the weight of an assumption, the unlikely it is to be true. To use penalization, the instance of the problem must include, besides H, M, and T , an n-tuple of weights W = w 1 , . . . , w n , where each w i is an integer number (the weight) associated to a variable h i ∈ H. The instance can thus be written W, H, M, T .
The considered orderings are formally defined as follows: Let us consider the use of these orderings on the running example. Prioritization allows for a further refinement of the set of solutions by exploiting the plausibility ordering over the hypotheses. For example, we may assume that the fact that package X is required and that we used the wrong version of the compiler are the two most likely hypotheses. Formally, they will be part of the first set of assumptions H 1 , while the other assumptions will therefore go in H 2 . Formally, the problem instance is now H 1 , H 2 , M, T . Both ⊆-prioritization and ≤-prioritization produce {p} and {v} as the only minimal explanations. This is because all other explanations either have a bigger intersection with H 2 , or an equal intersection with H 2 but a bigger intersection with H 1 .
Finally, penalization requires a weight (an integer number) for each hypothesis. Let us for example use the set of weights 4, 2, 4, 1 associated with the set of hypotheses a, p, t, v}. Since larger weights correspond to less likely hypotheses, we are assuming that our first and third hypotheses (a and t) are the least likely, while p is more likely and v is the most likely. From definition, the explanation {v} is the one having the least weight, and is therefore the only solution of the problem.
The basic problem of abduction is that of finding one or more explanations. However, we have already remarked that none may exist. Therefore, the first problem we consider is the existence one: given an instance of abduction, does an explanation exist? Another related problem is that of verifying, once a set of hypotheses has been found, whether it is really an explanation or not.
Other problems are related to the structure of the explanations. Namely, hypotheses that are in all explanations may considered as "sure" conclusions of the abductive process. On the other hand, hypotheses that are part of some explanations can be regarded as "possible" conclusions.
The formal definition of these questions as decision problems is as follows. Necessity: is h ∈ H in all, and at least one, minimal solution? That is, Dispensability: is h ∈ H such that either there is no solution or there exists one who does not contain h? That is, Dispensability is the converse of the problem of necessity, since an hypothesis h is dispensable if and only if it is not necessary. The problem of dispensability is not of much interest by itself, but is sometimes useful for simplifying the proofs.
Clearly, the ordering does not matter for the problem of existence, since we consider only well-founded orderings: therefore, an explanation exists if and only if a minimal explanation exists. For the other problems, the ordering must be taken into account. Different orderings may lead to different computational properties.
In this paper, we assume that T is a 3CNF formula: this assumption does not cause a loss of generality unless we want to assume that H ∪M = Var(T ).

Complexity and Compilability
The basic complexity classes of the polynomial hierarchy [Sto76,GJ79], such as P, NP, coNP, etc., are assumed known to the reader. We denote by C, C ′ , etc. arbitrary classes of the polynomial hierarchy. The length of a string x ∈ Σ * is denoted by ||x||.
We summarize some definitions and results proposed to formalize the online complexity of problems [CDLS02]. In computational complexity, problems whose solution can only be yes or no are the most commonly analyzed. Such problems are called decision problems. Any such problem can be formalized as set of strings, those whose solution is yes. For example, the problem of propositional satisfiability (deciding whether a formula is satisfiable or not) is characterized by the set of the strings that represent exactly all satisfiable formulae.
The strings that compose the set associated to a problem represent the possible problem instances that produce a positive solution. Problems like abduction, however, have instances that can be naturally broken into two parts: one part is known in advance (T and H) and one part is only known at run-time (M). Therefore, the instances of such problems are better encoded as pairs of strings. Therefore, a problem like abduction is formalized by a set of pairs of strings, rather than a set of strings. We define a language of pairs S as a subset of Σ * × Σ * .
The difference between the first and second element of a pair is that some preprocessing time can be spent on the first string alone. This is done to the aim of solving the problem faster when the second string comes to be known. While our final aim is to reduce the running time of this second phase, some constraints have to be put on the preprocessing phase. Namely, we impose its result to be of polynomial size. Poly-size function are introduced to this purpose: a function f from strings to strings is called poly-size if there exists a polynomial p such that, for all strings x, it holds ||f (x)|| ≤ p(||x||). An exception to this definition is when x represents a natural number: in this case, we impose ||f (x)|| ≤ p(x). Any polynomial function is polysize, but not viceversa. Indeed, a function g is poly-time if there exists a polynomial q such that, for all x, g(x) can be computed in time less than or equal to q(||x||). Clearly, the running time also bounds the size of the output string; on the other hand, even a function requiring exponential running time can produce a very short output. The definitions of polysize and polytime function extend to binary functions as usual.
Using the above definitions, we introduce a new hierarchy of classes of languages of pairs, the non-uniform compilability classes [CDLS02], denoted by ;C, where C is a generic uniform complexity class, such as P, NP, coNP, or Σ p 2 .
Definition 1 ( ;C classes, [CDLS02]) A language of pairs S ⊆ Σ * × Σ * belongs to ;C iff there exists a binary poly-size function f and a language of pairs S ′ ∈ C such that, for all x, y ∈ S, it holds: x, y ∈ S iff f (x, ||y||), y ∈ S ′ Clearly, any problem whose time complexity is in C is also in ;C: just take f (x, ||y||) = x and S ′ = S. Some problems in C however belongs to ;C ′ with C ′ ⊂ C; for example, some problem in NP are in ;Π p . These are in fact the problems we are most interested, as the preprocessing phase, running on x only, will produce f (x), which allows solving the problem in polynomial time. This is important if these problems cannot be solved in polynomial time without the preprocessing phase (e.g., they are NP-complete).
The class ;C generalizes the non-uniform class C/poly -i.e., C/poly ⊂ ;C -by allowing for a fixed part x. We extend the definition of polynomial reduction to a concept that can be used with these classes.
Definition 2 (Non-uniform comp-reduction) A non-uniform comp-reduction is a triple of functions f 1 , f 2 , g , where g is polytime and f 1 and f 2 are polysize. Given two problems A and B, A is non-uniformly comp-reducible to B (denoted by A ≤ nucomp B) iff there exists a non-uniform comp-reduction f 1 , f 2 , g such that, for every pair x, y it holds that x, y ∈ A if and only if f 1 (x, ||y||), g(f 2 (x, ||y||), y) ∈ B.
These reductions allows for a concept of hardness and completeness for the classes ;C.
Definition 3 ( ;C-completeness) Let S be a language of pairs and C a complexity class. S is ;C-hard iff for all problems A ∈ ;C we have that The hierarchy formed by the compilability classes is proper if and only if the polynomial hierarchy is proper [CDLS02, KL80, Yap83] -a fact widely conjectured to be true.
Informally, ;NP-hard problems are "not compilable to P". Indeed, if such compilation were possible, then it would be possible to define f as the function that takes the fixed part of the problem and gives the result of compilation (ignoring the size of the input), and S ′ as the language representing the on-line processing. This would implies that a ;NP-hard problem is in ;P, and this implies the collapse of the polynomial hierarchy. In general, a problem that is ;C-complete for a class C can be regarded as the "toughest" problem in C, in the assumption that preprocessing the fixed part is possible.
While ;C-completeness is adequate to show the compilability level of a given reasoning problem, proving it requires finding a nucomp reduction. We show a technique that let us reuse, with simple modifications, the polytime reductions that were used to prove the usual (uniform) hardness of the problem. Namely, we present sufficient conditions allowing for a polynomial reduction to imply the existence of a nucomp reduction [Lib01].
Let us assume that we know a polynomial reduction from the problem A to the problem B, and we want to prove the nucomp-hardness of B. Some conditions on A should hold, as well as a condition over the reduction. If all these conditions are verified, then there exists a nucomp reduction from * A to B.
Definition 4 (Classification Function) A classification function for a problem A is a polynomial function Class from instances of A to nonnegative integers, such that Class(y) ≤ ||y||.
Definition 5 (Representative Function) A representative function for a problem A is a polynomial function Repr from nonnegative integers to instances of A, such that Class(Repr(n)) = n, and that ||Repr(n)|| is bounded by some polynomial in n.

Definition 6 (Extension Function) An extension function for a problem
A is a polynomial function from instances of A and nonnegative integers to instances of A such that, for any y and n ≥ Class(y), the instance y ′ = Exte(y, n) satisfies the following conditions: Let us give some intuitions about these functions. Usually, an instance of a problem is composed of a set of objects combined in some way. For problems on boolean formulas, we have a set of variables combined to form a formula. For graph problems, we have a set of nodes, and the graph is indeed a set of edges, which are pairs of nodes. The classification function gives the number of objects in an instance. The representative function thus gives an instance with the given number of objects. This instance should be in some way "symmetric", in the sense that its elements should be interchangeable (this is because the representative function must be determined only from the number of objects.) Possible results of the representative function can be the set of all clauses of three literals over a given alphabet, the complete graph over a set of nodes, the graph with no edges, etc.
Let for example A be the problem of propositional satisfiability. We can take Class(F ) as the number of variables in the formula F , while Repr(n) can be the set of all clauses of three literals over an alphabet of n variables. Finally, a possible extension function is obtained by adding tautological clauses to an instance.
Note that these functions are related to the problem A only, and do not involve the specific problem B we want to prove hard, neither the specific reduction used. We now define a condition over the polytime reduction from A to B. Since B is a problem of pairs, we can define a reduction from A to B as a pair of polynomial functions r, h such that x ∈ A if and only if Definition 7 (Representative Equivalence) Given a problem A (having the above three functions), a problem of pairs B, and a polynomial reduction r, h from A to B, the condition of representative equivalence holds if, for any instance y of A, it holds: The condition of representative equivalence can be proved to imply that the problem B is ;C-hard, if A is C-hard [Lib01].

Compilability of Abduction: No Ordering
In this section we analyze the problems of existence of explanation, explanation verification, relevance, and necessity, for the basic case in which no ordering is defined. Formally, we want to determine whether the complexity of the problems related to SOL(H, M, T ) decrease thanks to the preprocessing step on H and T .
We first give an high-level explanation of the method we use to prove the incompilability of the considered problems. We begin by applying the method to the problem of existence of explanations, and then we used it for verification, relevance and necessity.

The Method
The problem of deciding whether there exists an explanation for a set of manifestations is Σ p 2 -hard [EG95]. Therefore, there exists a polynomial reduction from another Σ p 2 -hard problem to this one. In order to prove it is also ;Σ p 2 -hard we can show that the other problem has the three functions, and the reduction satisfies the condition of representative equivalence. Unfortunately, this is not the case. As a result, we have to look for another reduction.
Such a reduction should be as simple as possible. In general, the more similar two problems are, the easier it is to find a reduction. What is the Σ p 2 -hard problem that is the most similar to the problem of existence of explanation? Clearly, the problem itself is the most similar to itself.
The theorem of representative equivalence is indeed about a reduction between two problems A and B, but it does not forbid using the same problem: it only tells that, if we have a reduction from an arbitrary Σ p 2 -hard problem A to B, satisfying representative equivalence, then B is ;Σ p 2 -hard. Nothing prevent us from choosing A = B. This technique can be formalized as follows: • show that there exists a classification, representative, and extension functions for the problem B; • show that there exists a reduction from B to B satisfying representative equivalence.
The most obvious reduction from a problem to itself is the identity. In our case, however, identity does not satisfy the condition of representative equivalence. As a result, we have to look for another reduction.
Before showing the technical details of the reductions used, we point out an important feature of this technique. Since the condition of representative equivalence tells that B is ;C-hard if A is C-hard, using A = B we prove that B is ;C-hard whenever B is C-hard. This result holds even if a precise complexity characterization of B is not known. For example, if we only know that B is in Σ p 2 , but do not have any hardness result, we can still conclude In order to simplify the following proofs, we denote with Π(X) the set of all distinct clauses of length 3 on a given alphabet X = {x 1 , . . . , x n }. Since the theory T is in 3CNF by assumption, we have that T ⊆ Π(V ), where V is the set of variables appearing in T .

Existence of Solutions
In order to define a reduction from the problem of existence of solutions to itself, we first consider the function f from abduction instances to abduction instances defined as follows: In these formulae, X denotes the alphabet of T , while C and D are sets of new variables in one-to-one correspondence with the clauses in Π(H ∪ X). Note that, by definition, T is a subset of Π(H ∪ X). 1. We prove that The same holds for any d i ∈ R. This proves that S ′ ∩ (C ∪ D) ⊇ R.
Since R contains either c i or d i for any i, the same holds for S ′ . No other variable in C ∪D can be in S ′ , otherwise S ′ would be inconsistent with T ′ , which contains the clauses ¬c i ∨ ¬d i .
2. Let S ′ be an element of SOL( H ′ , M ′ , T ′ ). We prove that S = S ′ \(C ∪ D) ∈ SOL( H, M, T ). The point proved above shows that, for each i, S ′ contains either c i or d i , depending on whether γ i ∈ T . As a result: As a result, S ∪T is consistent because the above formula is. Moreover, since the above formula implies M, and each variable in C ∪ D appears only once, it also holds S ∪ T |= M. As a result, S is a solution of H, M, T .
3. Let S ∈ SOL( H, M, T ), and let The claim is thus proved.
This lemma shows that any abduction instance can be converted into another one in which the set H and the theory T only depends on the number of variables of the original instance. This reduction can be used to build a reduction satisfying the condition of representative equivalence. The extension function is also easy to give. For example, we may add to T a set of tautologies with new variables. We are now able to show a reduction satisfying the condition of representative equivalence. Let i be the reduction defined as follows. The following theorem is a consequence of the fact that i satisfies the condition of representative equivalence.

Verification
We We define two functions f ′ and g ′ c to be similar to the functions f and g c of the last section, except for the addition of a candidate explanation H a .
These functions can be composed to generate a function that satisfies representative equivalence. This way, we prove the nucomp-hardness of the problem of verification.

Relevance, Dispensability, and Necessity
We make the following simplifying assumption: given an instance of abduction H, M, T , where H = {h 1 , . . . , h m }, the problem is to decide whether the first assumption h 1 is relevant/dispensable/necessary. Clearly, the complexity of these problems is the same, as we can always rename the variables appropriately.
Theorem 3 The problems of relevance and dispensability with no ordering is ;Σ p 2 -hard, while necessity is ;Π p 2 -hard.
Proof. By Lemma 1 and Lemma 2, i( H, M, T ) is a reduction from the problem of relevance to the problem of relevance. Indeed, for any H a ⊆ H, the set

Compilability of Abduction: Preferences
In this section, we consider the problems of verification, relevance, and necessity when the ordering used is either ≤ or ⊆. These orderings have in common the fact that the instance of an abduction problem is simply a triple H, M, T , whereas the orderings of the next section employee classes of priority or weights that are part of the instances. The problem of existence is the same as with no ordering, as these orderings are well founded.

Some General Results
We give some general results about the problem of abduction in the case in which an ordering on explanation is given. In order to keep results as general as possible, we consider an arbitrary ordering satisfying the following natural conditions. We determine the compilability of abduction with preference in the same way we did in the case of no ordering: we show that the function i is a polynomial reduction from the problems of abduction to themselves, and that it satisfies the condition of representative equivalence. To this aim, we need the analogous of Lemma 1 and Lemma 2.

Lemma 3 If is a meaningful ordering, it holds:
We use the result of Lemma 1. Namely, since all solutions of f ( H, M, T ) coincide on C ∪ D, these variables are irrelevant thanks to the fact that is meaningful.
Formally, we have: This proves the claim.
We can also prove the analogous of Lemma 2. These lemmas can be used to prove incompilability of abduction when an irredundant and meaningful ordering is used.

Verification
We consider the problem of verifying whether a set of assumptions is a minimal explanation according to the orderings ≤ and ⊆. More generally, we prove the following theorem for any meaningful and irredundant ordering.
Theorem 4 If is a meaningful and irredundant ordering, verifying whether a set of assumptions is a minimal explanation is ;C-hard for any class C for which the problem is C-hard.
Proof. The same classification, representative, and extension functions used for the case of no ordering can be used for this case as well.
Let now consider the functions f ′ and g ′ c . From Lemma 3 and Lemma 4 it follows that they are reductions from the problem of verification to itself. Moreover, their composition i ′ satisfies representative equivalence.

Relevance, Dispensability, and Necessity
We make the following simplifying assumption: given an instance of abduction H, M, T , where H = {h 1 , . . . , h m }, the problem is to decide whether the first assumption h 1 is relevant/dispensable/necessary. There is no loss of generality in making this assumption. as we can always rename the variables appropriately.
Theorem 5 If is a meaningful and irredundant ordering, then the problems of relevance/dispensability/necessity are ;C-hard for any class C of the polynomial hierarchy for which they are C-hard.
Proof. From Lemma 3 and Lemma 4, it follows that the reduction i is a reduction from the problems of relevance/dispensability/necessity to themselves, if is meaningful and irredundant, and it also satisfies representative equivalence.
Since ⊆ and ≤ are meaningful irredundant orderings, their complexity implies their compilability characterization.

Compilability of Abduction: Prioritization and Penalization
We consider the cases in which the ordering over the explanations is defined in terms of a prioritization. The instances of the problem are different from those of the previous section, since H is replaced by a partition of assumptions H 1 , . . . , H m . In the cases of ≤-prioritization and ⊆-prioritization, the induced ordering is meaningful and irredundant. However, the results on meaningful irredundant ordering cannot be directly applied because, in Theorem 4 and Theorem 5, we assumed that the instances have the form H, M, T , while now they have the form H 1 , . . . , H m , M, T . Therefore, we have to find new classification, representative, and extension functions.
We first consider the problem of verification, and prove its nucomphardness. Then, we move to the problems of relevance, dispensability, and necessity. As for the case of ≤-preference and ⊆-preference, we employee a sort of normal form, in which the assumption we check is the first one.

Verification
First of all, we show the classification, representative, and extension functions for the problem of verification. The instances of the problem include a "candidate explanation" H a . These functions can be easily proved to be valid classification, representative, and extension functions. What is missing is a reduction from the problem of verification to itself satisfying the condition of representative equivalence.
To this extent, we use two functions f ′′ and g ′′ c that are similar to f and g c , respectively. In particular, f ( H 1 , . . . , H m , H Besides the partition of the assumptions, this is exactly the function used in Lemma 1. As a result, we have that: Since is a meaningful irredundant ordering, the same property holds replacing SOL with SOL . The last step is to define a function g ′′ c similar to g c . This is done as follows. Theorem 6 The problem of verification for any prioritization based on a meaningful and irredundant ordering is ;C-hard for any class C for which it is C-hard.
Proof. The composition of i ′′ of f ′′ and g ′′ c is a reduction satisfying representative equivalence.
i ′′ ( H 1 , . . . , H m , H a ,  The fact that is a reduction from the problem of verification to itself easily follows from the fact that both f ′′ and g ′′ c are. Moreover, the result of f (g ′′ Class( H 1 ,...,Hm ,Ha,M,T ) ( H 1 , . . . , H m , H a , M, T )) is an instance in which the number of classes of assumption, of variables in each class, and the number of other variables, all coincide with the class of the original instance. The function f ′′ produces an instance in which everything but M and H a depends only on these numbers. As a result , the function i produces an instance in which everything but M and H a depends on the class of the original instance only. As a result, this function i ′′ is a reduction from the problem of verification to itself, satisfying representative equivalence, which implies the incompilability of the problem.

Relevance and Necessity
We restrict the problems to the case the assumption we want to check for relevance/dispensability/necessity is the first variable of H 1 . The problems have the same complexity of the general ones (in which the assumption can be an arbitrary one.) This, however, cannot be proved with a simple renaming of the variables, as we did for the case of preference.
Theorem 7 Let be a meaningful and irredundant ordering. It holds: Proof. We first give an informal sketch of the proof. The set of solutions (with no ordering) of the first and the second instances only differ because the explanations for the second instances must contain either s or both h i j and t.
The explanations of the second instances are first compared on the assumptions in H 1 , . . . , H m , and then on {s, t}. Therefore, the ordering for the second instance is a refinement of the ordering of the first one. Namely, a minimal solution of the second instances is either a minimal solution of the first one plus s, or a minimal solution of the first one plus t. However, the latter is a solution only if it contains h i j . Therefore, the presence of a solution containing h i j in the first instance is equivalent to the presence of a solution for the second instance containing t.
The formal proof is as follows. Let H, M, T be the first instance and H ′ , M ′ , T be the second one.
This can be proved as follows. First, since S ′ ∪ T ′ is consistent, it follows that S ′ ∪ T is consistent as well (because T ⊆ T ′ ), which also implies that (S ′ \{s, t}) ∪ T is consistent.
Let us now prove that (S ′ \{s, t}) ∪ T |= M. By assumption, we have S ′ ∪ T ′ |= M ′ . The following chain of implications leads to the claim. First of all, S ∪ {t} is solution of the second instance. What is left to prove is its minimality. This is also easy: removing t leads to a set of assumptions which does not explain v. If removing some variable from S leads to another solution, then S is not minimal.
. The "if" direction is easy. Let us assume that S is a minimal solution of the first instance. Then S ∪ {s} is a solution of the second one. Let us prove that it is minimal. We cannot remove variables from S, otherwise S would be not minimal. As a result, the only other possible explanations that can be preferred are S ∪ {t} and S ∪ ∅. None of them is a solution, because they do not imply u.
It is now possible to prove the claim. If there exists a minimal solution of the first instance containing h i j , then there exists a minimal solution of the second one containing t. On the other hand, if no minimal solution contains h i j , then all corresponding minimal solutions of the second instances contains s, which means that t is in none of them. Therefore, relevance and necessity of h i j on the first instance are equivalent to relevance and necessity, respectively, of t in the second instance.
As a result of this theorem, we can assume that relevance or dispensability are evaluated w.r.t. the first variable in H 1 . In order to prove that these problems are not compilable, we give a classification, representative, and extension function. where r = |V ar(T )\(H 1 ∪ · · · ∪ H m )| Given these three functions, all is needed is a reduction from the problem of relevance to itself satisfying representative equivalence. The function i ′′ cannot be used only because the instance it deals with contains the set of assumptions H a . However, removing this part of the instance both from its argument and its result, we obtain a reduction with the right properties. We can thus conclude that the problems of relevance, dispensability, and necessity are incompilable.
Theorem 8 Let be a meaningful and irredundant ordering. The problems of relevance, dispensability, and necessity for the problem of prioritized abduction are ;C-hard for any class C of the polynomial hierarchy for which these problems are C-hard.
As a result, we easily obtain the compilability properties of the problem of prioritized abduction using the orderings ⊆ and ≤.
Theorem 9 Relevance and dispensability are ;Σ p 3 -hard if ⊆ is used, and ;∆ p 3 -hard if ≤ is used instead.
The compilability of relevance and dispensability in the case of penalization is an easy consequence of the last theorem, as relevance with ≤ (prioritized) can be directly translated (using a nucomp reduction) to relevance with penalization.
Corollary 2 Relevance and dispensability are ;∆ p 3 -hard, in the case of penalization.

The Horn Case
The Horn case can be dealt with using the same technique of the general case. Since, however, only Horn clauses are allowed, each time we use Π(H ∪ X), which contains all clauses of three literals over H ∪ X, we have to replace it with the Π H (H ∪ X) that contains all Horn clauses of three literals over the set H ∪ X. The reductions we used employ clauses ¬c i ∨ ¬d i and ¬c i ∨ γ i , which are Horn if γ i is Horn. The reduction used in Theorem 7 also involves Horn clauses only. Therefore, all results holding for the general case hold for the Horn case as well. Namely, all problems about Horn clauses are ;C-hard for the same classes C they are C-hard. An important feature of reduction from the same problem is that it allows proving nucomp-hardness result even for a restriction of the problem, provided that these reduction do not transform an instance into a non-valid one (e.g., unless an Horn instance is mapped into a non-Horn one.) The even more restricted case of definite Horn clauses, however, cannot be dealt with in the same manner. Indeed, the clauses ¬c i ∨ ¬d i , are not definite. Some problems, however, becomes polynomial, in this case. Namely, all problems in the case of no order are polynomial, as well as necessity for ⊆-preference. We only show that a reduction for the case of ≤-preference. As before, the problem is that of checking whether h 1 is in an explanation of minimal size of H, M, T . Since h 1 is part of H, we regard H, M, T as being the instance of the problem. The classification, representative, and extension functions are as usual (tautologies are definite Horn clauses.) The reduction we use is based on the following function f , where n = |H|.
The idea is simply that of replicating each variable c j i for n + 1 times. This way, if S ⊆ H, then a clause γ i holds in S ∪ T only if S contains all clauses c j i . The reduction is based on the following two facts: Let us first assume that S is an explanation of H, M, T , that is, is therefore an explanation because the latter set is indeed M ′ . The set C ′ is not relevant to this part of the proof.
Let us now assume that S ′ = S ∪ {c j i | γ i ∈ T } ∪ C ′ is an explanation of f ( H, M, T ). Since |C ′ | ≤ n, then S ′ does not contain all c j i for any i. Therefore, all clauses that are not in T contains at least an unassigned c j i in S ′ ∪ T ′ . Therefore, these clauses are cannot be used to derive a single literal in M ′ . As a result, S ∪ {c j i | γ i ∈ T } ∪ T ′ |= M ′ . This is equivalent to S ∪ T |= M, that is, S is an explanation of H, M, T .
This lemma can be used to relate the minimal explanations of the two instances. Proof. The lemma above implies that S is an explanation if and only if S ∪ {c j i | γ i ∈ T } is an explanation, as this is the case of C ′ = ∅. Let us now prove that the minimality of these two explanations coincide.
Let us first assume that S is a minimal explanation. We prove that S ′ = S ∪ {c j i | γ i ∈ T } is a minimal explanation of H ′ , M ′ , T ′ . By the lemma above, S ′ is an explanation; we have therefore only left to prove that it is of minimal size. Assume that S ′′ is another explanation of H ′ , M ′ , T ′ . By construction, S ′′ contains {c j i | γ i ∈ T }. Therefore, S ′′ can be smaller than S ′ only if S ′′ \{c j i | γ i ∈ T } is smaller than S ′ \{c j i | γ i ∈ T }. Since the latter coincide with S ′ ∩ H, whose size is bounded by n, we have that |S ′′ \{c j i | γ i ∈ T }| ≤ n. Therefore, S ′′ can be written as S ′′ = S ′′′ ∪ {c j i | γ i ∈ T } ∪ C ′ with |S ′′′ ∪ C ′ | < |S|. The latter inequality implies |C ′ | < n: by the lemma above, S ′′′ would be an explanation of H, M, T . Since |S ′′′ ∪ C ′ | < |S|, then |S ′′′ | < |S|, that is, S is not be minimal.
Let us now assume that S ′ = S ∪ {c j i | γ i ∈ T } is a minimal explanation of H ′ , M ′ , T ′ , and prove that S is a minimal explanation of H, M, T . Assume, indeed, that S ′′ is a smaller explanation of H, M, T . By the lemma above, S ′′ ∪{c j i | γ i ∈ T } would then be an explanation of H ′ , M ′ , T ′ smaller than S ′ .
The reduction can be defined as for the Horn case, by taking into account the fact that the original instance H, M, T may not have any explanation. Such a reduction ratifies the condition of representative equivalence, thus proving that problems about ≤-preference are ;C-hard whenever they are C-hard. Similar reductions can be defined for the other orderings.

Conclusions
In this paper, we have shown that logic-based abduction cannot be simplified by preprocessing the theory T and the hypotheses H. In particular, this result holds for various kinds of explanation orderings, and also for the Horn restriction. These results have been proved using the technique of representative equivalence [Lib01]; since reductions are from a problem to itself, they prove that a problem is "compilability-hard" for any class for which it is hard. In other words, we did not prove that a problem is hard for some class, but rather that it complexity decreases thanks to preprocessing. Using these "self-reductions" allows for proving such a result even if the complexity of the problem is not known. For example, we prove that a preprocessing step does not simplify the problem of finding a minimal explanation for any ordering that is both meaningful and irredundant. The complexity of this problem is not known for all such orderings; moreover, it depends on the ordering itself.
The technique we used to prove that "preprocessing does not simplify abduction", being based on complexity classes at last, should however not be considered as implying that preprocessing is not useful for speeding up solving of abduction problems. Indeed, as for any result based on the theory of NP-completeness, this conclusion only holds as a worst-case result. In other words, it does not tell that no instance can ever by made simpler by preprocessing, but simply that any preprocessing procedure necessarily has some hard instances that are not simplified. In a sense, our result is more positive than it appears, as it tells that a worst-case exponential on-line algorithm is reasonable, given than no worst-case polynomial one exists.
Compilability results based on hardness and reductions have consequences similar to complexity results based on the theory of NP-completeness: they tell that, since no worst-case polynomial algorithm can solve the problem, alternative directions have to be considered. Approximation is one example: the preprocessing phase may result in some data structure that allows a better (or faster) approximation of the best abductive explanations. Another possible direction is that of incomplete compilation, in which the preprocessing phase produces a result that is only useful in some cases, but not always. Another common solution to hard-to-compile problems is that of generating a worst-case exponential preprocessing result. This approach is especially useful if part of the result can be used, as we can then try to generate it and use only the part we can store. All these alternative approaches, however, only make sense when the impossibility of preprocessing the problem into a polynomial problem has been proved. This is the practical impact of our hardness results.
Finally, compilability has been proved to be related to expressibility of logical formalisms, that is, their ability of representing information in little space [CDLS00]. Logical-based abduction formalisms could then be characterized by the set of abductive problems they are able to express. Compilation classes (and not complexity ones) have been proved useful to this aim.


Wavelet kernels on a DSP: a comparison between lifting and filter banks for image coding

We develop wavelet engines on a digital signal processors (DSP) platform, the target application being image and intraframe video compression by means of the forthcoming JPEG2000 and Motion-JPEG2000 standards. We describe two implementations, based on the lifting scheme and the filter bank scheme, respectively, and we present experimental results on code profiling. In particular, we address the following problems: (1) evaluating the execution speed of a wavelet engine on a modern DSP; (2) comparing the actual execution speed of the lifting scheme and the filter bank scheme with the theoretical results; (3) using the on-board direct memory access (DMA) to possibly optimize the execution speed. The results allow to assess the performance of a modern DSP in the image coding task, as well as to compare the lifting and filter bank performance in a realistic application scenario. Finally, guidelines for optimizing the code efficiency are provided by investigating the possible use of the on-board DMA.

INTRODUCTION
A huge number of applications use the discrete wavelet transform (DWT) [1] as a means to extract relevant features from signals. Examples are reported in the fields of mathematics, physics, numerical computing, and engineering, including image classification, feature detection, image denoising, image registration, and image compression, just to mention a few. Especially in the engineering field, there has been a con-siderable interest in using wavelet transforms for image and video coding applications [2,3]. As a result, the ISO/ITU-T has selected the DWT as the transform coding kernel for the new image compression standard, namely JPEG2000 [4], which will be released during 2001. Consequently, fast and cost-effective implementations of DWT kernels, compliant with JPEG2000 specifications, are called for in order to make its diffusion as widespread as possible.
While the wavelet transform of an image can be fairly easily computed by means of a general-purpose personal computer, there obviously exist contexts where more compact, light-weight and less power-demanding computing devices are required. A recent trend [5] fosters the design of reconfigurable systems that make use of digital signal processors (DSPs) and field-programmable gate array (FPGA). An example is given by the transmission of images from scientific space missions, where the images collected by the onboard sensors may undergo wavelet-based compression (e.g., Rosetta Osiris [6]), with a DSP-based system being used as computational core. DSPs are also very often used to handle image and video processing tasks in consumer electronics [7]. The importance of wavelets on a DSP is witnessed by the number of implementations proposed in the literature (cf. [8,9]). In this paper, we focus on the study of the DSPbased implementation of a wavelet kernel; the target application is image coding with JPEG2000, with its extension to intraframe video coding (Motion-JPEG2000). Until recently, DWT implementations were based on the so-called filter bank scheme [1], which computes the DWT of a signal by iterating a sequence of highpass and lowpass filtering steps, followed by downsampling. In 1997 Sweldens proposed a new scheme, called lifting scheme (LS), as an alternative way to compute the DWT [10]. The LS has immediately obtained a noteworthy success, as it provides several advantages with respect to the filter bank scheme. The most interesting ones from the implementation standpoint are that (i) the LS requires less operations than the filter bank scheme, with a saving of up to one half for very long filters; (ii) the LS allows to compute an integer wavelet transform (IWT), that is, a wavelet transform that maps integers to integers [11], thus enabling the design of embedded lossless and lossy image encoders [12,13].
This paper is focused on the development of a wavelet kernel based on the LS, and using a DSP as the computational core. The interest of this work is manifold. Firstly, from a pure implementation perspective, the performance evaluation of an optimized implementation of such a kernel on a modern DSP indicates the maximum sustainable processing rate. This can be used to estimate the number of images per second that can be processed by, for example, a compression engine such as JPEG2000, or the video frame rate that can be sustained by a Motion-JPEG2000 encoder/decoder in DSPbased applications, for example, videoconferencing by means of a PC card. Secondly, since the LS can be used to design a progressive lossy-to-lossless compression algorithm [13], it is important to evaluate the execution speed of the IWT with respect to the DWT. Thirdly, and distinctively novel in this paper, from a signal processing point of view, there is a strong interest in finding out to which degree the theoretically lower complexity of the LS translates into reduced execution speed; in fact, it is likely that the DSP architecture affects the performance of lifting and filter bank wavelet cores in a different fashion. In this work all aspects are considered, that is, an optimized DSP implementation of the LS is presented, and its performance is then compared with that of the fil-G ter bank scheme; both DWT and IWT are considered. The results allow to assess the impact of the DSP architecture on the performance of both algorithms, thus providing useful guidelines for the architectural design and implementation of a wavelet-based processing system. This paper is organized as follows. In Section 2, we briefly review the wavelet transform, focusing on the filter bank scheme and the LS in Sections 2.1 and 2.2, respectively. The DSP implementations of both algorithms are described in Section 3. In Section 4, a performance evaluation of such implementations is proposed; in particular, results related to the execution speed are reported in Section 4.1, and a comparison between LS and filter bank scheme is presented in Section 4.2. The possibility of improving performance by means of direct memory access (DMA) is discussed in Section 4.3. Finally, in Section 5 conclusions are drawn.

WAVELET TRANSFORM
As already stated, the two main algorithms used to compute the DWT are the filter bank scheme and the LS, which are briefly reviewed in Sections 2.1 and 2.2, respectively.

Filter bank scheme
The filter bank scheme (see [1]) is sketched in Figure 1, where the operations needed to compute the DWT of a onedimensional signal are depicted. One level of decomposition involves that the input sequence is highpass and lowpass filtered by the analysis filtersH(z) andG(z); the two resulting sequences are then downsampled by a factor two. More decomposition levels can be obtained by iterating this procedure on the lowpass branch, as shown in Figure 1. The twodimensional extension is achieved by filtering and downsampling first along the rows, and then along the columns. The inverse transform is achieved performing a similar sequence of filtering and upsampling operations (see [1]).

Lifting scheme
As well known [1], a discrete-time filter can be represented by its polyphase matrix, which is built from the ᐆ transforms of the even and odd samples of its impulse response. The LS stems from the observation [14] that the polyphase matrix can be factorized, leading to the implementation of one step of the filter bank scheme as a cascade of shorter filters, which act on the even and odd signal samples, followed by a normalization. In particular, the LS performs a sequence of primal and dual lifting steps, as described in the following and reported in the block diagram of Figure 2. The inverse transform is achieved performing the same steps in reversed order [14].
The polyphase representation of a discrete-time filter H(z) is defined as where H e (z) and H o (z) are respectively obtained from the even and odd coefficients of h[n] = ᐆ −1 {H(z)}, where ᐆ denotes the zeta transform. The synthesis filters H(z) and G(z) (lowpass and highpass, respectively) can thus be expressed in terms of their polyphase matrix andP(z) can be analogously defined for the analysis filters. The Euclidean algorithm [14] can be used to decompose P(z) andP(z) as This factorization leads to the sequence of primal and dual lifting steps shown in Figure 2.
The filters H e (z), H o (z), G e (z), and G o (z), along with their analysis counterparts, are Laurent polynomials [14]. Since the set of all Laurent polynomials exhibits a commutative ring structure, within which polynomial division with remainder is possible, long division between two Laurent polynomials is not a unique operation [14]. Therefore, several different factorizations (i.e., pairs of {s i (z)} and {t i (z)} filters) may exist for each wavelet. However, in case of DWT implementation, all possible choices are equivalent.
An IWT, mapping integers onto integers, can be very simply achieved rounding off the output of the s i (z) and t i (z) filters right before adding or subtracting [11]; the rounding operation introduces a nonlinearity in each filter operation. As a consequence, in the IWT the choice of the factorization impacts on both lossless and lossy compression, so making the transition from the DWT to the IWT not straightforward [15].
As already stated, the LS requires fewer operations than the filter bank scheme. The latter algorithm corresponds to merely applying the polyphase matrix: only the samples that are not discarded by the subsequent downsampling operation are actually filtered. In order to compare the two algorithms, one can use the number of multiplications and additions required to output a pair of samples, one on the lowpass and one on the highpass branch. As shown in [14], the cost of lifting tends, asymptotically for long filters, to one-half of the cost of the standard algorithm. Table 1 reports the formulas, presented in [14], to compute the cost of the two algorithms for the filters used in this work (see also Section 3). Here |h| and |g| are the degree of the highpass and lowpass filter (i.e., the number of coefficients minus one); in the case that |h| and |g| are even, we set |h| = 2N and |g| = 2M. Note that the filter SWE (13,7), being an interpolating filter, has a different formula, which also involves the number of vanishing momentsÑ.

IMPLEMENTATION
The LS and filter bank scheme have been implemented on the floating-point Texas Instruments TMS320C6711 DSP board. The board comprises a 150 MHz floating-point processor, two memory regions, namely on-chip and off-chip, a direct memory access (DMA) controller, and some peripherals interfaces. The CPU core includes two sets of 16 registers (register file A, register file B), the on-chip memory divided into two cache memories (L1, L2), and the arithmetic and logical units (see [16]). Figure 3 shows the block diagram of the DSP architecture.
In the following, we outline some features of our implementation of the two algorithms, including the filters and types of boundary extensions used. The LS implementation is compliant with the specifications of the Final Committee Draft of JPEG2000 Part I (core coding systems) [4], which is,  at the time of this writing, the latest publicly available document describing the standard. The code profiling results for the two algorithms, reported in Section 4, have been obtained demanding the optimization of the assembler code to the C compiler, which is known to nearly achieve the same efficiency as an expert programmer. For this reason, the code has been written in a simple and plain style, so as to facilitate compiler optimization. Therefore, in this section we only give an overview of the implementations of the two algorithms, whereas we rather concentrate on the profiling results (Section 4), which represent the main contribution of this article. Of course, one could achieve some performance improvement by constraining the implementations, for example, to support a limited number of filters (even only one); nevertheless, this approach would negatively impact on generality of application, which in this work has been preserved as far as possible.
As for boundary extension at the borders of the input signal, which is necessary because the wavelet filters are noncausal, two possible extensions are considered.
(i) Symmetric extension: it performs mirroring of the signal samples outside the signal support. If used with biorthogonal symmetric filters, it allows to achieve perfect reconstruction also at the image borders.
(ii) Zero padding: it consists in adding zeros before and after the signal. This extension is not supported by the JPEG2000 standard, but is very simple, and hence sometimes used.
The first two filters are explicitly embodied in JPEG2000, for the reversible and nonreversible transform, respectively.    Note that the last filter is not supported by JPEG2000 Part I. However, it has been considered because, being a long filter, it allows to verify the asymptotic complexity of the LS. The selection of the factorization of the wavelet filters, to be used in the LS, has been made following the directives of the JPEG2000 standard, and is reported in Tables 2,  3, and 4. The filter length, deducible from the acronym, allows to easily identify the N and M parameters previously defined.
As for the filter bank scheme, the input signal is filtered by the same kernels listed above, but using the expanded rather than the factorized representation. Notice that, while performing the convolution between the signal and the filter impulse response, the samples that would be discarded by downsampling are not computed at all. For completeness, Tables 5, 6, and 7 report the coefficients of the filters employed, up to the fourth decimal digit.

EXPERIMENTAL RESULTS
As stated in Section 1, the objective of this work is manifold; in particular, experimental tests have been carried out with the following goals.
(1) To evaluate the absolute running time of an LS-based wavelet kernel on a modern DSP; in particular, in view of  the implementation of an embedded lossy-to-lossless image compression system, to understand to which degree embodying an IWT capability may penalize the execution speed. This matter is discussed in Section 4.1.
(2) To find out how close to the theoretical value is the actual performance gain of the LS with respect to the filter bank scheme, in terms of execution speed. This matter is discussed in Section 4.2.
(3) To study the possibility of exploiting an available onboard DMA, in order to speed up code execution. This matter is discussed in Section 4.3.
The results shown in the following, and the comparison between LS and filter bank scheme, have been reported (see Sections 4.1 and 4.2) in terms of the time needed to perform one level of transform on one image row; this has been done so as to facilitate the interpretation of results. The results have been parameterized on the length of the input data vector, and execution times for dyadic lengths are reported. It has been found that the sum of such dyadic values yields a very accurate estimate of the multilevel transform. Of course, computing the wavelet transform of an image requires to perform both rowwise and columnwise filtering. However, it has been found that the time needed to compute a columnwise filtering is the same as for rowwise filtering. Even though this behavior might seem surprising at a first glance, it can be reasonably justified by the efficient management of memory accesses performed by the cache memory; a more detailed explanation is given in Section 4.3.

Absolute running times
The graphs in Figures 4, 5, and 6 report the absolute running times achieved by the LS (in the DWT and IWT mode, respectively) and the filter bank scheme, in order to compute the one-level wavelet transform of a one-dimensional data vector, contiguously stored in the external memory. The boundary extension used is the symmetric one.
The results reported on the graphs can be used to estimate the number of images per second that can be processed by these algorithms. Employing the LEG(5,3) filter and the symmetric extension for a complete 2D one-level decomposition on a 256 × 256 grey-scale image, the LS allows to process between 7 and 8 images per second, whereas the filter bank scheme only sustains between 4 and 5 images per second. Note that computing the IWT, rounding off the filtered coefficients in the LS, leads to slower operation. The running times of the IWT are from 10% to 25% larger than the DWT using the LS.
If the wavelet kernel is thought of as the core of a JPEG2000 encoder, it is worth recalling that the wavelet transform is responsible for a significant part of the total encoder and decoder running time. Some figures have been obtained by profiling the Jasper reference JPEG2000 implementation, and have been reported in [17]. It turns out that, for progressive lossless coding, the wavelet transform is responsible of about 30% of the overall encoder and decoder running time. In the progressive lossy case this percentage is increased to about 50% at the encoder, and 70% at the decoder. This implies that it should be possible to encode/decode, with a single DSP, about 2 256 × 256 images per second in the integer lossless mode (using the LEG(5,3) filter), and encode and decode about 2 images per second in the lossy mode using the DB(9,7) filter. While this figures are suitable for an image coding application, it turns out that more powerful hardware, such as a multi-DSP system or an FPGA, is required to sustain real-time Motion-JPEG2000 video.

Comparison between lifting and filter bank
As stated, in [14] it is claimed that the LS requires asymptotically half the number of operations with respect to the filter bank scheme. We have compared the running time of our LS and filter bank implementations, in order to understand how the DSP architecture impacts on the performance gain. In particular, Table 8 reports the ratios between the running time of the filter bank scheme and the LS. Comparing these figures with the theoretical results, it can be noticed that these ratios are different from the theoretical values.
This behavior can be explained considering the architectural features of the processor employed. The DSP used in this work has an efficient pipeline, which can dispatch 8 parallel instructions per cycle. Parallel instructions proceed simultaneously through each pipeline phase, whereas serial instructions proceed through the pipeline with a fixed relative phase difference between instructions. Every time a jump to an instruction not belonging to the pipeline occurs, the pipeline must be emptied and reloaded. Thus, in this case, the filtering operations that frequently update the pipeline    contents, turn out to be disadvantaged. The effect on the computation of the wavelet transform is that, in general, the convolution with a long kernel can be optimized more efficiently than several convolutions with short kernels. Therefore there is a trade-off, in that the filter bank must perform twice as many operations as the LS with long filters; on the other hand, the use of the pipeline tampers with the LS operation, since the factorizations of long filters may consist of numerous short filters. The best results, with regard to the gain, are obtained with the SWE(13,7) filter: even though the filter is long, its factorization consists of only 2 filters, with 4 coefficients each. 1 The opposite occurs with the DB(9,7) filter, whose factorization consists of 4 filters with 2 coefficients each. The gain that comes from the inferior number of operations in LS is thus lost in emptying and reloading the pipeline. The LEG(5,3) filter has an intermediate behavior. Note that, for an increasing number of samples, the ratio between the running times of the two algorithms is not constant, nor it increases linearly. This behavior is due to the way the processor manages the cache memory and the data transfer from external to internal memory.

Optimization with DMA
The results in Section 4.2 have shown that the LS is faster than the filter bank scheme as for the computation of the wavelet transform. These results have been obtained using implementations which demand to the CPU the data transfer from the external memory to the CPU itself for performing the convolutions. In the following, we focus on the architectural features of the DSP employed, investigating the possibility of improving the LS performance by exploiting the properties of the DMA, typically available on a DSP board. The LS program previously described filters a vector of coefficients allocated on a region of external (off-chip) memory. On the other hand, the DSP has a two-level internal (onchip) cache, with significantly lower access time than the external one. The second-level cache (L2) can be configured as internal memory, and can be used to store and filter the image pixels values, with an expected speedup due to the reduced memory access time.
Since the size of an image is usually larger than the L2 size, it is necessary to transfer the data in small blocks from the external to the internal memory. The device used to this purpose is the DMA controller. In this work, the DMA has been configured so as to transfer a row (or column) of the image into the on-chip memory, while at the same time the CPU filters the data transferred at the previous step. In this way, the CPU never accesses the off-chip memory, since both the stack and the temporary variables are allocated in L2. The use of L2 as a shared resource between DMA and CPU involves the need of synchronizing these devices. The data can be corrupted if the accesses to L2 do not take place in the correct order. To avoid this problem, we have employed four software interrupts to regulate the sequence of operations. Moreover, the two concurrent devices are set to operate on two different buffers, which are swapped at each filtering cycle with a ping-pong buffering mechanism (see Figure 7).
We have run this version of the LS on a 512 × 512 greyscale image, performing one complete 2D decomposition level with the DB (9,7) filter. This has led to the results shown in Table 9, where the running time of the standard LS algorithm is also reported for comparison. It can be noticed that the synchronization of the devices and the reconfiguration of the DMA after each transfer leads to a higher running time. In order to make the employment of DMA and L2 advantageous, it is necessary to reduce the number of DMA reconfigurations. This can be done by transferring more than one row or column at one time. Table 10 shows that transferring, for example, 2 or 4 rows simultaneously yields an improvement of the LS performance. However, the gain is not as high as expected, and hardly pays back for the additional complexity. The reason for such low gain using the DMA lies in the efficiency of the DSP cache memory.
In fact, every time the CPU needs a datum stored in the external memory, 32 consecutive bytes are transferred from the memory to L1. If the offset between two data processed sequentially by the CPU is fewer than 32 bytes (i.e., 8 floating-point coefficients), the CPU accesses the memory only once, since the second datum will be already cached in L1. The advantage of accessing a faster memory is apparent only when the weight of the memory accesses is high overall. We assume that the image pixel values are stored in the ex-  ternal memory as floating-point values in row major order. As for rowwise filtering, one access to the external memory is sufficient to retrieve eight samples of the to-be-filtered data.
As far as columnwise filtering is concerned, once a complete image column has been retrieved from the external memory, the subsequent seven columns are also placed in the cache. 2 Moreover, in the specific case of the wavelet transform, most of the time is spent by the processor in computing the convolution, that is, sums and products between the filter coefficients and the image pixel values; the filtering routine is computationally heavy, so that the weight of the access operations is not very high. Therefore the actual number of accesses to the external memory turns out to be quite limited, and their weight on the program running time accordingly low. In summary, the performance improvement in the wavelet transform computation, which can be obtained by employing the DMA, is limited because of the efficiency of the on-chip cache.

CONCLUSIONS
In this paper, we have addressed the development of wavelet cores on a DSP, compatible with the JPEG2000 specifications.
The wavelet transform has been implemented according to the filter bank scheme and the lifting scheme; in this latter case the integer-transform option has also been considered. The code has been profiled so as to evaluate the efficiency of the implementation and, more interestingly, to allow a comparison between the LS and the filter bank scheme. Moreover, the use of the DMA has also been considered as a possible way to improve data throughput. The results have highlighted some aspects of DSP-based implementations of the wavelet transform, which are discussed in the following.
(1) The DSP considered in this work is able to compute up to 8 complete 2D one-level wavelet transforms per second on a grey-scale 256 × 256 image. This figure can be used to evaluate the number of JPEG2000 frames that a single DSP is able to code or decode, for example, using the JPEG2000 profiling results reported in [17].
(2) A performance comparison between lifting and filter banks has been carried out. We have found that the LS always runs faster than the filter bank scheme. However, the performance gain differs from the theoretical results in [14], because the DSP architecture has a different impact on code optimization for the two algorithms. In particular, convolutions with long filters, which are typical of the filter bank scheme, tend to benefit from the DSP pipelined architecture. On the other hand, the LS gain is higher for long filters. In the end, the actual gain heavily depends on the number and length of the factorized filters used in the LS.
(3) It has turned out that employing the DMA to transfer data from the external to the internal memory (and vice versa), while the CPU concurrently filters the previously transferred data, may provide very little advantage, if any at all, in terms of execution speed. This is due to the fact that the on-chip cache memory is able to very efficiently manage the data transfer operations, for both rowwise and columnwise filtering.

ACKNOWLEDGMENT
This work was partially developed under the Texas Instruments Elite program. Marco Grangetto received the "summa cum laude" degree in electrical engineering at Politecnico di Torino in 1999, where he is currently pursuing a Ph.D. degree. His research interests are in the field of digital signal processing and multimedia communications. In particular, he is working at the development of efficient and low complexity lossy and lossless image encoders based on wavelet transforms. Moreover, he is challenging the design of reliable multimedia delivery systems for tetherless lossy packet networking. He was awarded the Premio Optime by "Unione industriale di Torino" in September 2000, and a Fulbright grant in 2001 for a research period at the Center for Wireless Communications (CWC) at UCSD.


extfieldsofstudy:
Physics
Computer Science

text:
An Automatic Image Reduction Pipeline for the Advanced Camera for Surveys

We have written an automatic image processing pipeline for the Advanced Camera for Surveys (ACS) Guaranteed Time Observation (GTO) program. The pipeline, known as Apsis, supports the different cameras available on the ACS instrument and is written in Python with a flexible object-oriented design that simplifies the incorporation of new pipeline modules. The processing steps include empirical determination of image offsets and rotation, cosmic ray rejection, image combination using the drizzle routine called via the STScI Pyraf package, object detection and photometry using SExtractor, and photometric redshift estimation in the event of multiple bandpasses. The products are encapsulated in XML markup for automated ingestion into the ACS Team archive.

Introduction and Basic Operation
The ACS science team was apportioned about 550 orbits of GTO time in exchange for its instrument development and calibration work. A robust and flexible astronomical data reduction and analysis pipeline was required for processing these data and other observations for which the science team is responsible. To fill this need, we developed a package called "Apsis" (ACS pipeline science investigation software), written in the Python programming language using a flexible, modular design. Apsis was used for processing the ACS early release observation (ERO) images of the Tadpole and Mice galaxies, the Cone Nebula, and M17 soon after ACS was installed on the Hubble Space Telescope. Since then, it has developed and been used extensively on Linux and Solaris platforms for processing WFC and HRC data from both science and calibration programs.
A given processing run starts with flat-fielded multi-extension FITS images that have been processed through the CALACS software at STScI (Hack 1999). The basic Apsis "observation object" consists of all the images of a given program field (or mosaic of adjacent fields). These are grouped into separate "associations" according to the different imaging/grism filters used or (sometimes) different epochs, and FITS tables are constructed similar to those used in STScI OPUS pipeline. Reading and manipulation of FITS images and tables are done with the aid of the PyFits and Numarray Python modules, and any IRAF/STSDAS routines are called through Pyraf (see Greenfield et al. 2002). Other external programs are accessed via system calls.
The observation object is then passed to the various python modules in succession, which have "methods" (python functions) for performing the following general tasks: image offset measurement corrected for distortion, sky estimation and subtraction, cosmic ray (CR) rejection and "drizzling," construction of error arrays and a multi-band "detection image," object detection and measurement, photometric calibration, and photo-z estimation. A running log keeps track of progress and records diagnostics. After completion, each module object is written to disk as a byte stream using the Python "pickling" utility; this allows for recovery of information in the event of failure and simplifies debugging. The modules also contain detailed methods for producing XML messages and markup of the data products (images and catalogs) for archiving purposes.
Although Apsis was designed primarily as an automated pipeline, it can be run by users as a standalone program, and provides a suite of commandline options for this purpose. These include switches for turning off various parts of the processing (e.g., sky subtraction, cataloging), specifying a particular input image as reference for the shifts, supplying an alternate distortion model, externally measured shifts, or sky values, lowering the CR rejection thresholds, changing the output image pixels scale, and several other options. The following sections provide a few details on the major processing steps.

Image Registration and Sky Subtraction
The align module determines the relative x, y shifts and rotations, as well as the sky levels, of the input images. SExtractor (Bertin & Arnout 1996) is run with a signal-to-noise threshold of 10 on each science extension of each image (there are two science extensions for WFC; one for HRC and SBC). The resultant catalogs are culled on the basis of object size and shape parameters, thereby rejecting the vast majority of cosmic rays and CCD artifacts as well as overly diffuse objects. If fewer than ten "good" sources remain, then SExtractor is rerun at lower thresholds. The x, y coordinates of each "good" source are corrected using the distortion model read from the IDCTAB FITS table specified in the image headers or on the command line. Sources from different extensions (different CCD chips) of the same image are placed on a common rectified frame using the IDCTAB parameters V2REF and V3REF.
We use the "Match" program (Richmond 2002) to derive shifts and rotations with respect to a reference image, by default the one having the most "good" sources. We modified Match to accept an input guessed transformation (derived from the headers) and to report more diagnostics for evaluating the success of the matching. In the event of failure, Match is rerun without an input guess, using the full triangle-matching search algorithm on the N brightest sources; this is repeated with larger N , and an N 6 hit in processor time, if necessary. All sources are used for tuning up the final transformation once it is found. We also evaluate the median x, y shifts for all matched sources, and we revert to these if the derived rotation is negligible.
This automatic, adaptive matching procedure works quite well in practice. Images taken at large offsets and in different visits can have header shift errors of ∼ 1 ′′ (∼ 20 WFC pixels), but this is irrelevant for the triangle matching algorithm. Typical WFC GTO fields produce one-to-several hundred matched sources per exposure, and the resulting shift uncertainty is typically ∼ 0.02 pix.
Problems have only occurred for some images of blank fields taken with the HRC, which has an area 1/64 of the WFC. In this case Apsis defaults to the header shifts, although it is also possible to supply external shifts. Grism (G800L) images are by default aligned with direct images according to the headers.
The sky values and sigmas returned by SExtractor for each image extension are used as inputs to the STSDAS dither.sky task, which in turn uses the STS-DAS gstatistics routine. However, experimentation indicated that the mean sky levels reported by SExtractor were more robust, although tended to be biased high in more crowded fields. For this reason, we adopt the SExtractor sky value when it is the lower estimate, and the mean of the two otherwise. The sky is then subtracted, with the option of averaging the values for different extensions of the same image. This step removes sky level differences for the image combination and CR rejection routines described in the following section.

Image Combination
The modules combDither and pyblot combine all exposures within each filter into a single geometrically corrected image while rejecting cosmic rays. This is done through the STSDAS Dither package drizzle-blot-drizzle cycle outlined by Gonzaga et al. (1998), although here coded in Python. First the images are "drizzled" to separate output images using the shifts and rotations supplied by the Apsis align module. These individually drizzled images are then median stacked using exposure time weighting and a 'minmax' clipping algorithm. The median image is then "blotted" back to each of the input image positions, rescaled in exposure time, and used as a template for CR rejection with the driz cr task. The driz cr parameters were optimized to achieve good CR rejection without harming the centers of any stars. In particular, this meant setting the derivative scale parameter to a value near unity.
A cosmic ray mask is produced for each science extension and is multiplied by the bad pixel mask that we produce from the data quality arrays using a call to Pydrizzle with the 'bits' parameter set to 8578 to include 'good', 'replaced', 'saturated,' and 'repaired' pixels (see Hack 1999). These combined CR/badpix masks are then used for the final drizzling of the input images in each filter to a single output image. We again use the shifts and rotations found by align and produce drizzled images in units of electrons. In so doing, it is necessary to divide the output pixel values by the number of science extensions, since the drizzle task does not recognize the different extensions as being part of the same image. The default drizzle pixfrac and scale parameters are unity but can be reset with flags on the Apsis command line.
After the final images are produced, the image headers are thoroughly updated and corrected. This includes calculating new CD matrices from scratch based on the output pixel scale and image orientation, which is derived through spherical geometry from the PA V3 header keyword of the reference image, the declination, and the detector orientation and location in the V2,V3 plane. The code also ensures that all of the output images have identical WCS information, as they should all be well aligned at this stage. At this writing, the WCS zero points are off by roughly 2 ′′ due to systematic pointing errors, but this is expected to improve with a recent FGS realignment.
We produce an "RMS image" for each output science image. The RMS images have pixel values equal to the estimated error per pixel, based on the total read noise, signal level, Apsis cosmic ray rejection, and the effects of the multiple bias and dark frame subtractions. The actual root-mean-square pixel variation in the science image is of course lower due to the noise correlation induced by non-integer shifts and geometric correction. However, we verified that the RMS images reflect the pixel variation when images are stacked without shifting or correction. The RMS images are used in estimating photometric errors.

Object Detection, Photometry, and Redshift Estimation
A series of modules do the object photometry. The combFilter module produces a multi-band "detection image," which is the variance-weighted average of the science images in the different bandpasses. Images in specific filters (e.g., grism, polarizers) can be omitted from this average. This module also produces a detection weight image, which is a similarly weighted sum of the exposure maps from the drizzling process. The detectionCatalog and filterCatalog modules create parameter files and run SExtractor, first on the detection image alone, and then multiple times in "dual image mode." In dual mode, the detection image defines the object position and apertures, but the photometric measurements are done on the filter image with its associated RMS image.
The colorCatalog module derives the photometric zero points from the image header catalogs, sorts through the different SExtractor catalogs, and produces a single, calibrated multicolor catalog. It also uses simple logic for flagging apparently bad or anomalous magnitudes. Finally, the photoz module feeds the multicolor catalog to the Bayesian Photometric Redshift package (Benítez 2000), which is itself coded in Python. A final XML "run message" is written in the same format as the individual module messages. The images and XML catalogs can then be ingested into the ACS team data archive.