We present a novel image filter generation method and an image filter retrieval algorithm and analyse their properties. Based on an original image and a filtered version of the original, the retrieval algorithm can find, to a high probability, which filter was applied to the original from a large pre-defined list of filters, without having to apply all filters to the original image, which is usually a time consuming task when the number of filters is large. This is achieved by pre-computing image annotations for a set of filtered images obtained by applying the pre-defined filters to a database of 50 images. Using standard imagebased annotation techniques, we show that the filter retrieval can be achieved by taking the closest images to the original from the database and analysing those known images instead. The retrieval algorithm has a set of parameters and we present results of experiments with these values to maximise the probability of retrieving the correct filter.
Image filtering [
To determine good methods for searching for filters, we work with 1000 image filters of our own devising, as described in §2. In §3, we describe the retrieval methods we have experimented with, and in §4, we describe our experiments and the results. We conclude that – at least with the 1000 image filters we have been working with – it is possible to retrieve a filter given a single image produced by it, to a high degree of probability. We further discuss some future directions, including the application of machine learning techniques to this problem. 2
Our database consists of 1000 image filters, each of which can be represented as a
tree of fundamental (unary) image transform such as inverse, lookup, threshold,
colour addition, median, etc., and also (binary) image compositors such as add,
and, divide, fade, max, min, multiply, or, subtract, xor, etc., as described in [
An image is a function I : {0, . . . , N } × {0, . . . , M } → {0, . . . , 255}3, for some N and M . The set of all images will be denoted by I. A filter is a function F : I → I. The set of all filters will be denoted by F . The symbol F (I) will then stand for the application of filter F to image I.
An annotation2 of dimension d is a function A : I → Rd. The set of all annotations of dimension d is denoted by Ad and the set of all annotations is defined as A = ∪d∞=1Ad. Writing Pz = {(w1, . . . , wz ) ∈ Rz|∀i.0 ≤ wi ≤ 1 ∧ iz=1 wi = 1}, we define a set of weighted annotations to be a pair (A0, w) such that A0 ∈ A and w ∈ P|A0|. The set of all weighted annotations is denoted by W.
Let I be an image, (A0, w) a set of weighted annotations and A ∈ A0 an annotation of dimension d. The Rd vector A(I) is called the annotation of I via A or an A-annotated image. We can introduce metrics in the space of A-annotations using any existing metric for Rd. For example, we may define the distance between two images, I and J , as the weighted Euclidean distance between pairs of real vectors Ak(I) and Ak(J ) for each Ak ∈ A0:
D(A0,w)(I, J ) = wk · d(Ak(I), Ak(J )) (1) |A0| k=1 where d is the usual Euclidean distance. We will use the symbol 2X , where X is a set, to denote the power set of X . 3.2
The problem we address here is as follows: given (i) an image I ∈ I, (ii) a set of filters F0 and (iii) a filtered version of I, I = F (I), for some F ∈ F0, determine the filter F . A straightforward na¨ıve algorithm to solve this problem is shown below. The Na¨ıve algorithm simply applies all filters to the user image and checks which filter achieves the same end image. The problem with this na¨ıve algorithm is that we are generally interested in the case where F0 is a large set 1 On a MacOs X machine running at 2.6Ghz. 2 An annotation is a vector of what are usually called features of an image, which in turn are real values computed from that image.
Filter(ID : 2I , FD : 2F ) : 2I 1. IF ← ∅ 2. for each I ∈ ID 1. for each F ∈ FD
1. IF ← IF ∪ {F (I)} 3. return IF
Na¨ıve(FD : 2F , IU : I, IU : I) : FD 1. IF ← Filter({IU }, FD) 2. for each I ∈ vF 1. if I = IU 1. F ← filter which produced I 2. return F and applying thousands of filters to an image is very time consuming. Moreover, we are interested in finding an efficient algorithm for the above problem for the case where the filter retrieval operation is to be performed repeatedly. So, we can concede some initial offline computation time if we can have fast retrieval thereafter. 3.3
We will now present a general algorithm to perform such filter retrieval, which is described below in pseudo-code. We start with a database of images, ID, and filters, FD, a set of weighted annotations (A0, w) and three integers which parameterise the algorithm. We start by choosing a random sample of size O of the image database ID and choose the N images of that sample which are closest to the user image, IU . We denote this set of closest images by C. Note that the distance between two images I and J is measured here as the weighted Euclidean distance between their annotations obtained via A0, as described by Equation (1). We then retrieve the filters which, applied to the images in C, yield images closest to the user-given filtered image, IU . This set of filters FR is then returned. Given an integer K, a set X and a function f : X → R. The set argminxK∈X {f (x)} represents the K values of x which yield minimum values for f (x). If multiple values of x yield the same minimum value for f , we take the resulting set to be the union of all those values of x.
Retrieve(ID : I, FD : F, (A0, w) : W, (N, O, T ) ∈ N3) : FD 1. S ← randomSample(O, ID) 2. C ← argminIN∈S{P|kA=01| wk · d(Ak(I), Ak(IU ))} 3. FR ← argminTF ∈FD {PI∈C P|kA=01| wk · d(Ak(F (I)), Ak(IU ))} 4. return FR
In the algorithm, given an image I, we write Ak(I) to be the kth-annotation of I. Note that, in this algorithm, all images in the database have been previously filtered and both original and filtered images have been annotated beforehand. This means that at retrieval time both Ak(I) and Ak(F (I)) are known and no calculations are needed other than Euclidean distances between vectors. The only annotations to compute at retrieval time are Ak(IU ) and Ak(IU ).
The Retrieve algorithm can be assessed by choosing particular parameters and comparing the retrieval accuracy and retrieval time. For ID, we hand-picked 50 images from the Corel Stock Photo Library illustrating a wide range of everyday images, including portraits and full-body pictures of men and women, cityscapes and countryside scenes, among others. For FD we took the set of 1000 filters described in §2. These filters represent a broad sample of the filter space F .
The set of annotations A0 chosen consists of four main modes of
operation of the Annotate software, which has been used as an automated image
annotation system using global features in [
Having made these choices, the only remaining parameters of the Retrieve algorithm were N , O, T and the set of four weights, w. To study this space of parameters, we implemented the Retrieve algorithm and, for different choices of the parameters, we measured the proportion of times that the correct filter was found in the set of filters returned by the algorithm.
We started by studying the space of weights, [
For this particular set of weights, w = (0.005, 0.465, 0.530, 0), we assessed how the remaining parameters affected the probability of correct retrieval, with the results given in figure 2. We carried out three different sets of experiments: (i) we fix O = 10, 50 and computed the probability of correct retrieval for varying N = 1, 2, 3, 5, 10, 25, 50 and T = 1, 5, 10, 25, 50 (each different value of T produces one curve and each choice of O is shown in a different graph); (ii) we fixed T = 10, 50 and computed the probability of correct retrieval for varying N = 1, 2, 3, 5, 10, 25, 50 and O = 1, 2, 3, 5, 10, 25, 50 (each different value of O produces one curve and each choice of T is shown in a different graph); (iii) we fixed N = 2 and computed the probability of correct retrieval for varying O = 2, 3, 5, 10, 25, 50 and T = 1, 5, 10, 25, 50 (each different value of T produces one curve). In the sixth graph of figure 2, we show the retrieval times which correspond to the setting of experiment (i) with O = 10.
From the first set of experiments (fixed O) we see that there is a maximum for the parameter N and that it is generally attained for either N = 2 or N = 3. This is particularly clear in the O = 50 graph. So, we conclude that it is good to have more than one image to compare the user’s image to but that using more than 3 images degrades the subsequent comparison of annotations. We can also confirm that increasing T always improves retrieval success. This was expected since returning more filters increases the probability that they contain the correct filter but it shows us that the difference in results from taking T = 25 or T = 50 is small. Even for T = 10, the difference is still acceptable and this choice seems to be a good compromise between probability of correct retrieval and the amount of filters that the user still has to choose from after the retrieval. For (N, O, T ) = (3, 50, 10), the probability of the required filter being present in the 10 retrieved filters is 0.928.
From the second set of experiments (fixed T ), we see that increasing O always achieves better results, which is expected since greater O means a larger image database to work with and therefore more likelihood of finding an image which is closer to the image provided by the user. Once again, there is a maximum for N around 2 or 3 except for very small O where the initial database is so small that in fact, it is better just to keep the closest image in the database. From the third experiment (fixed N ) we see that for N = 2, both increasing either T or O always increases retrieval success as before. In the sixth graph in figure 2 we present retrieval times corresponding to the first experiment with O = 10. We see that retrieval times lie in the range 10 − 40 ms, are hardly affected by T , and increase roughly linearly with N . For larger values of O (not shown) retrieval times increase considerably but never raise above 300 ms. We will not therefore emphasise comparison between retrieval times for the different parameters as for practical purposes of user retrieval, the times are small (between 10 − 300 ms). We did not compute retrieval time for the Na¨ıve algorithm as it is clear from the algorithm’s definition that retrieval times will be dominated by the filter application times which, when applied 1000 times, will add up to several minutes. In future, we will apply the Na¨ıve algorithm to the filters returned by Retrieve, which will improve accuracy, but only degrade efficiency slightly.
Finally, we considered the scenario N = O separately. This can be seen as equivalent to the case where the user only provides the Retrieve algorithm with the filtered image IU but not the original image IU . If we do not know the original image, we can simply pick one or more random images from the database and compare their filtered versions to the filtered user image. This amounts to changing the second line of the Retrieve algorithm to C ← S. The results of this case are shown in the final graph of figure 2 for N = O = 1, 2, 3, 4, 5, 10, 20, 30, 40, 50 and T = 1, 5, 10, 25. We see that considering more than 5 images in the database most of the times does not add to the retrieval probability and that for T = 10, the probability now drops to around 0.727, but if the user chooses from 50 retrieved filters (T = 50), the probability is 0.914.
We have presented an image-filter retrieval algorithm which takes a user-given image and filtered version of the image and retrieves a set of 10 filters (from 1000) which contains the applied filter with a probability of 0.928 in a fraction of a second. The retrieval algorithm has 7 parameters and we have showed how its behaviour is affected by changing these parameters. We find the best choice for 3 parameters and near best choices for the remaining 4. We also show that the method can retrieve the correct filter even if the original (unfiltered) image is not given, albeit with a smaller probability of success.
In future, we plan to study how different distance metrics in step 2 of
Retrieve affects its performance. Moreover, we will study how the choice of
image database may influence the probability of correct retrieval by repeating the
same experiments with different sets of images. We also plan to address the more
general problem of learning a set of properties for a required filter (or filters)
given a set of images and/or filters that the user has chosen through a browsing
mechanism. In particular, we will use mathematical theory formation [
We wish to acknowledge the excellent work of Imperial College masters students George Lin and Chi-Tou Yip for their investigations into evolving image filters. We would also like to thank Jo˜ao Magalha˜es for his extensive input on the usage of the Annotate software. This research is funded by EPSRC grant EP/F067127.
Probability and retrieval correct times retrieval for experiments (i), and five
O = 10 graph). weights were set of correct retrieval for N =
O. Parameter n
30 t=50 4
6 Parameter n 8 10