{'fraction_non_alphanumeric': 0.03536357986326911, 'fraction_numerical': 0.010068365444375388, 'mean_word_length': 4.680277712402918, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Probabilistic Saliency Estimation

In this paper, we model the salient object detection problem under a probabilistic framework encoding the boundary connectivity saliency cue and smoothness constraints in an optimization problem. We show that this problem has a closed form global optimum which estimates the salient object. We further show that along with the probabilistic framework, the proposed method also enjoys a wide range of interpretations, i.e. graph cut, diffusion maps and one-class classification. With an analysis according to these interpretations, we also find that our proposed method provides approximations to the global optimum to another criterion that integrates local/global contrast and large area saliency cues. The proposed approach achieves mostly leading performance compared to the state-of-the-art algorithms over a large set of salient object detection datasets including around 17k images for several evaluation metrics. Furthermore, the computational complexity of the proposed method is favorable/comparable to many state-of-the-art techniques.


I. INTRODUCTION
Salient object detection is a computer vision research topic with growing interest over the last decade. The goal is to highlight the visually interesting regions in a given scene. The problem of saliency detection has been motivated by related work in neuroscience; humans select important visual information based on attention mechanisms in the brain [1]. Given this motivation, earlier works on saliency detection concentrate more on predicting sparse human eye-gaze points that are detected by eyetrackers [2]. Accordingly, most of the research on this track is based on biologically inspired algorithms which try to imitate the dynamics of the human attention mechanism [2]- [9]. During the last few years another related track emerged where the goal is to segment out salient objects [10]- [20], instead of predicting some sparse eye-fixations. Both research tracks produce saliency maps that are useful for tasks such as video surveillance [21], compression [22], image manipulation [23], automatic image cropping [24], foreground detection [25], and coding [26], to name a few. However, the output of salient object detector techniques is more useful, when compared to eye fixation predictions, for higher level computer vision and pattern recognition C. Aytekin Probabilistic Saliency Estimation Caglar Aytekin, Alexandros Iosifidis and Moncef Gabbouj tasks such as tracking [27], object region proposals [29] and object recognition [28].
In this paper, we focus on the salient object detection task. Since ultimately we consider salient object detection as a preprocessing block for higher level tasks as mentioned above, fast and generic methods would be preferred. Therefore, in this work we focus on unsupervised salient object detection. While supervised approaches, such as those in [45] and [36], have the potential of finding more accurate results, their performance depends on the training process followed and the data that has been exploited for training. Recent works have also indicated that unsupervised saliency detection approaches can compete (or even outperform) supervised methods [43].
Unsupervised salient object detection methods can be categorized based on the saliency cues they use. Commonly exploited cues include local and global contrast, boundary connectivity, shape and location cues. The local contrast cue is based on the assumption that the salient object is in contrast with its immediate surroundings [11], [12], [15], [20]. A spectral foreground detection method was proposed in [20] which optimizes a criterion involving the minimization of cut-value, which is equivalent to the maximization of the local contrast. A region contrast based method was proposed in [11], which computes a salient region as a weighted sum of local contrasts with its surroundings. The global contrast cue is similarly defined as by assuming that the salient object is in high contrast with its surrounding. A histogram-based method enhancing regions with global contrast to the rest of the image was proposed in [11]. The boundary connectivity prior is one of the most widely used cues and is based on the assumption that most of the image boundaries will not contain parts of the salient object [10], [15], [16], [20], [39]. There are many ways to use this prior. For example in [20], the boundary pixels were strongly assigned to background in a belief vector, which was a part of the optimization problem used to extract salient regions. A robust background assignment on image boundaries was conducted in [15] based on a handcrafted measure that differentiates foreground and background regions touching the boundary. The boundary regions were used as background templates in [10] to re-construct the image in a sparse and dense way. Salient regions were defined as the ones that have high reconstruction errors [10]. In [16], boundary regions were defined as absorbing nodes in a Markov chain model. The saliency values of each region were evaluated based on the absorption time of the regions by the boundary nodes. Similar to the boundary connectivity cue, the center prior also assumes that salient objects are less likely to touch the image boundaries. However, it makes a stronger assumption that the object is mostly located in the center of the image. Although this is not a very reliable cue, it was used in [12] as a weighting coefficient on local contrast based saliency maps.
The salient object detection methods can also be categorized according to their interpretation of saliency. One of the most popular interpretations is modelling saliency as a diffusion process [14], [16], [39]. These methods assume a preliminary > REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 3 information on saliency and designs several diffusion matrices to propagate this initial information to the whole salient region.
Another interpretation of saliency is a graph-cut based one, where the salient object is considered as a foreground partition which constitutes a large area and a high contrast with the background partition [19], [20], [29]. The concepts behind these interpretations, i.e. diffusion maps and graph partitioning were shown to be related in an earlier work [38].
For an extensive survey on the recent state-of-the-art salient object detection algorithms, readers are encouraged to see [37].
Furthermore, an extensive benchmark comparing the performance of the state-of-the-art in salient object detection is also provided in [43].
In this paper, we model the salient object detection problem by following a probabilistic approach. We propose an unsupervised salient object detection method (which we call Probabilistic Saliency Estimation -PSE) that jointly optimizes saliency cues such as boundary connectivity and smoothness constraints. The solution of the proposed optimization problem is shown to have a closed-form. Moreover, we show that, along with the proposed probabilistic framework, this solution can also be interpreted from several perspectives, including spectral graph cut, diffusion and one-class classification approaches, all leading to the exact same solution. By further exploiting these links, we show that some diffusion based [14], [16], [39] and spectral graph based [20] salient object detection methods can also be cast into the proposed probabilistic framework, which provides us a theoretical platform for comparison of our method with them. Based on the above analysis provided in this paper, we also show that the proposed PSE method differentiates from our previous methods [19], [20] from three aspects. First, it introduces a new formulation for saliency detection in a probabilistic framework. Second, by exploiting the graph-cut interpretation of PSE, we show that it also provides another approximation of the optimization criterion exploited in [19], [20] with looser constraints. Finally, we show that [19], [20] are suboptimal when they are investigated in the proposed probabilistic framework.
The main contributions of the paper can be listed as follows: -A novel probabilistic approach to the unsupervised salient object detection problem is proposed. Following this approach, we formulate a novel optimization problem and we show that it has a global optimal solution (PSE), leading to state-ofthe-art performance for unsupervised salient object detection. (Section II) -Based on the links observed between the proposed solution and those of diffusion based salient object detection methods, we interpret PSE as a diffusion based method. (Section II.B) -Based on the analysis of diffusion interpretation of PSE, we show that its solution involves terms related to graph cut.
Therefore, PSE can also be interpreted as a solution to the graph-based cut problem. In fact, we show that PSE can be derived directly from the original graph based cut problem. (Section II.C) -We show that some diffusion based and graph based methods can be cast into our proposed probabilistic framework under > REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 4 some assumptions. (Appendices A,B) -Finally, we show that the saliency detection problem can be interpreted as a one-class classification problem, whose solution is also given by PSE. (Section II.D) The rest of the manuscript is organized as follows. In Section II, we introduce the proposed PSE method and explore its connections and differences to a wide range of salient object detection methods, namely the diffusion, the graph-based, and the one-class classification approaches. In Section III, we present extensive experiments conducted on publically available datasets and compare the performance of the proposed method with the state-of-the-art. Finally, we conclude the paper in Section IV.

II. PROBABILISTIC SALIENCY ESTIMATION
We formulate the salient object detection problem as that of the estimation of the probability mass function (PMF) (x) of a random variable x, where a region/pixel in an image is a possible outcome of the event. Since the summation over the PMF is constraint to be equal to 1, such a formulation allows us to set the total attention given to the scene as fixed which is analogous to the limited processing capability of the human brain. Accordingly, a study on the mechanisms of visual attention in the human cortex [1] states that: "A typical scene contains many different objects that, because of the limited processing capacity of the visual system, compete for neural representation". The probabilistic framework allows us to model such competition by defining an event as drawing distinct regions from the image, where (x) defines the probability mass function of this event such that (x= )is high if the region is salient. Within this framework, we wish (x) to satisfy some properties related to the widely used saliency assumptions. For example, we expect similar probabilities for the image regions that are similar in a feature space, such as a color space. This is in accordance with the smoothness constraints for saliency as explained above. Furthermore, we wish to design (x) in such a way that any prior information about the PMF can be considered. For example, in this way one can make use of the widely accepted assumption that image boundaries are more likely to belong to the non-salient region.
Therefore, the estimation of (x) can be formulated as an optimization problem that involves two terms: one that enforces similar regions in a given feature space to have similar probabilities and another that encodes any prior information about the PMF. We express this joint optimization as follows: In (1), the first term suppresses the probability of a region if there is prior information that this region belongs to a non-salient > REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 5 region. This belief is encoded as a positive value. The second term in (1) forces two regions and to have similar probabilities if their similarity , in a feature space is high. Here, we avoid using an additional parameter for the regularization of the two terms in this optimization problem, since this regularization can be encoded by scaling the values of . For any symmetric similarity function, i.e. when , = , , one can rewrite (1) as follows: In order to simplify the notation, let us introduce a vector having elements = (x= ). Let us also define a diagonal matrix having elements [ ] = . Then, we can rewrite (2) in matrix form as follows: * = ( ) In (3), = − + , where is a matrix containing the similarity values , and is a diagonal matrix whose elements are obtained as [ ] = ∑ , .
In order to obtain the optimal solution of the optimization problem in (3), we calculate the saddle points of the Lagrangian given by: Partial derivative of ℒ( , ) with respect to is zero at the saddle points. We can formulate this as follows: By solving (5), we obtain a single saddle point as follows: * = 1 = q( ) . The normalization term q( ) = in (6) follows from the constraint =1. Next, we perform the second derivative test to validate that the saddle point (6) is indeed the global minimum of the optimization problem in (3): Following from (7), if is positive definite, i.e. it has a positive determinant, the second derivative test guarantees that the saddle point (6) is the global minimum of (4). Following the definition of , i.e. = − + and the symmetric property of , we observe that − is a positive semi-definite matrix. Then, any diagonal matrix with non-negative entries and at least one positive entry guarantees to be positive definite. In other words, prior information encoded in should correspond to a non-salient region and we should have this prior for at least one region.
A constraint that should be satisfied is that all the elements of * should be non-negative, which follows from the definition of probability. In order to enforce this constraint, one could include an additional constraint in (3). However, positivity of * is already guaranteed from the following facts: (i) is a positive definite matrix, hence the normalization factor in (6) is always positive, i.e., >0, (ii) is a positive definite -matrix [48], hence is a non-negative matrix [48] which yields nonnegativity of the numerator of (6). Finally, the normalization term q( ) scales the values of * , so that * =1. Therefore, * is guaranteed to be a valid probability vector.
We define the saliency of each region/pixel as proportional to its probability given by the optimal probability mass function * in (6). Therefore, to speed up computations, we can simplify the expression of saliency by removing the positive normalization term q( ) in (6), as follows: * = . boundaries most likely correspond to background regions [19]. Using such an assumption, we can simply set the diagonal elements of that correspond to image boundaries high and leave the rest as zero.
Next, we make an interesting observation from the closed form solution in (8) and note its similarity to the solution of the diffusion based salient object detection methods. We then discuss this similarity and show that PSE can be interpreted as a diffusion based method.

A. Analysis of Diffusion Based Methods
The saliency detection problem can alternatively be cast as a diffusion problem. A general representation of such algorithms is provided in [39]. This representation is formulated as follows: = .
The saliency map is calculated by multiplying a seed vector with a diffusion matrix . The seed vector is a prior confidence map for saliency. Various diffusion matrices have been used, such as ( − ) in [14] and ( − ) in [16].
By comparing (8) and (9), one can state that PSE is a diffusion based method using a diffusion matrix and a seed vector .
In Appendix A, we investigate why our proposed diffusion matrix and seed vector produce better saliency maps when compared to other diffusion methods, following a probabilistic approach.

B. PSE as a Diffusion Based Method and Links to Graph-Cut
First, let us review a recent finding about diffusion based methods. In [39], it was shown that in diffusion based methods, elements of saliency map were evaluated by a weighted sum of seed vector , where weights are defined as similarities of diffusion maps given by: In (10), and denote the eigenvector and eigenvalue of the diffusion matrix , respectively. The diffusion map Ψ was defined in [38] as a coordinate system where the Euclidian distance at this coordinate system gives the distance between the probabilities of the states of a Markov Chain at time .
Following our observation in the previous subsection related to the similarity between (8) and (9), PSE can be defined as a diffusion based method where the diffusion matrix is and the seed vector is = . Thus, we can rewrite (10) for PSE as follows: By analyzing (11), the saliency value of an element is obtained by summing the similarities of the diffusion map of to all diffusion maps at = −1/2, i.e., the similarities of the spectral feature vector of to all feature vectors. As in (10), the spectral feature vector is obtained by concatenating the element of the eigenvectors of , where each eigenvector is weighted by the inverse square-root of the corresponding eigenvalue as a measure of confidence.
Besides the above interpretation, a striking similarity of (11) to one particular spectral foreground detection problem, namely QCut [19] is revealed. In fact, the first term in (11) corresponds to a weighted sum of QCut's saliency maps resulting from exploiting the entire eigen-spectrum (a multispectral approach). In the original work [19], instead of a multispectral approach, only the eigenvector with the corresponding eigenvalue was exploited. However, a multispectral approach was later proved to produce a pool of high quality salient object proposals [29]. In the first term of (11), each QCut saliency map generated from a given eigenvector was weighted with the inverse of the corresponding eigenvalue, which is meaningful because the eigenvalue defines a cost function related to saliency [19]. Next, let us investigate the meaning of the second term of (11). For this, we have to know the structure of the eigenvectors of H. According to QCut's formulation, the squared magnitudes of these eigenvectors are already good indicators of saliency. Hence, it is reasonable to expect the eigenvectors to have high amplitudes in salient regions and close to zero values in non-salient regions. Due to the phase penalty term in QCut, we also expect the entries of the eigenvector to carry the same sign within the same object (i.e. all entries are either non-negative or non-positive). In the light of this information, the second term in (11) turns out to be an enhancement term on QCut's result. Salient objects found by QCut are enhanced by the contribution of the inner product with other salient nodes. Note that due to our assumption that the signs of eigenvectors within the object are the same, we can safely assume that the inner-product is positive; hence this is a reinforcement on the initial saliency maps. Furthermore, if there are two far-away salient objects (whose entries carry different signs) this term will eventually suppress the object with the smaller area. This is reasonable because larger regions are expected to be more salient than smaller ones. In the extreme case, if the area of one object is too small, the object can be considered as noise, and will hence be suppressed. Here we should note that some methods resort to post-processing in order to suppress small objects.
In order to illustrate the effect of the second term in (11) on the saliency map, let us consider the example images shown in Fig.   1. First, we use the first eigenvector of to illustrate the effect of the second term on the saliency map. Next, we use the entire eigen-spectrum, which is simply PSE, to highlight the contribution from other eigenvectors. The difference between the use of the first eigenvector and QCut is also illustrated in order to visualize the effect of the enforcement term in (11). We can observe that all elements having non-zero saliency are enhanced with respect to their initial confidence obtained by QCut. In this sense, we can state that although we do not make use of a seed vector , inherently PSE uses a similar confidence weighting where the confidence is determined by the QCut saliency maps. By the above analysis, we have observed that the solution of PSE involves enhanced multispectral solutions to an approximation of spectral graph-cut problem [19]. In the next section, we prove that PSE itself is yet another approximation to this specific problem.

C. PSE as a Graph-Cut Method
Following the local and global contrast cues, boundary connectivity and large area cues, a salient object is defined as a collection of pixels (or superpixels) suitably represented on a graph optimizing the following criterion [19].
is the cost of cutting the edges connecting segment to the rest of the graph A .
When edge weights , are defined as affinities, cut-cost can be considered as a measure of contrast. Furthermore, one can add an artificial background node to exploit the boundary cue where every node is connected to the background node with confidence v . One can re-write (12) with a binary saliency indicator vector as follows: * = argmin Eq. (13) can be rewritten in matrix form by defining = − + . * = argmin The optimization problem in (14) is NP-hard. Even if the values of are relaxed to have real values, the resulting function is discontinuous at = and the minimum occurs at → −∞. Obviously, this has no meaning in terms of approximation of the original problem. In [19], the cost function in (14) was written in the following form: * = argmin which is equivalent to (14) as long as ∀ ,y ∈ {0,1}. Then, a spectral approximation of this problem was solved by introducing a vector z that satisfies = ∘ . Adding a cost of ∑ w , z z −z z , to restrict the solution space of by penalizing sign changes, the approximation of (15) introduced in [19] can be re-written as follows: Solving the above optimization problem is equivalent to solving the following problem: Eq. (17) can be solved via eigen-analysis on , when is relaxed to have real values. This solution has theoretical connections to quantum mechanics and can be interpreted as a probability distribution of a sub-atomic particle's whereabouts in space, and the resulting method was thus called Quantum Cuts (QCut) [19].
Next, we show that PSE provides another approximation to (12) using the representation in (13) with looser constraints than QCut. We set only the constraint =1, which can be expressed as =1. We drop all other constraints, i.e., = ∘ and the phase-penalty term, and write the new minimization problem that approximates the original problem (13) as follows: * = argmin . (18) Notice that (18) is equivalent to (3). Hence, we have shown that PSE provides another approximation with looser constraints, when compared to [19], of the graph node cutting problem in (12) and * = * .
QCut and PSE approximations of the optimization problem in (12) can be formulated as follows: where E is the minimum eigenvalue of . At first glance, we may observe that both approximations can be related if one would rewrite * considering the eigen-decomposition of . This was indeed the analysis we made in the previous subsection where we have already shown the benefits of PSE compared to QCut. In Appendix B, we will make another theoretical comparison between QCut and PSE by giving a probabilistic interpretation of QCut and showing the shortcomings of the method in this framework. As the final connection to other approaches, we will show that PSE is also a solution to a one-class classification problem defined for saliency object detection, in the next subsection.

D. PSE as a One-Class Classifier
Let us consider the following problem: Given an image, find a projection vector that will map each image element in a feature space to a fixed value, hence modelling the image with a fixed value. This corresponds to finding a classifier that learns to predict if any feature from a broader set of images fits well to the modelled image or not. Note that this is a one-class classification problem, where we try to map the positive class to a constant value [46]. Let us denote the D-dimensional features of the image as ∈ℝ , =1,…, where is the number of regions in the image. Now let us represent these features in a space using a non-linear mapping function (. ), such that ∈ℝ → ( )∈ , = 1,…, . Let us also define the matrix = [ ( ),…, ( )].
By using this notation, let us denote by ∈ a vector mapping the representations of in to a fixed value, e.g. the value 1.
can be obtained by solving the following optimization problem: * = ( ( ) − 1) . (20) In matrix form, we can also rewrite it as follows: Since, in general, ( ) ∈ cannot be obtained, one exploits the Representer Theorem [47] stating that can be expressed as a linear combination of ( ) ∈ , i.e. = , where ∈ℝ is a vector encoding the contribution of each image region's features to . Finally, we can rewrite the problem as follows: The solution of (22) is given by * =( ) . In standard kernel-based one-class classification, the matrix is replaced by the positive semi-definite kernel matrix [49]. Note that matrix defined in our probabilistic saliency estimation method is positive definite and hence it can be expressed as = .
Comparing the solution of (22) with (8), we can observe that the proposed probabilistic saliency estimation method can be interpreted as a method solving the above one-class classification problem.
The interpretation given above implies that if an optimal vector that projects each feature of an image to a single value is found, and if this projection vector is represented as a linear combination of features from the image, then the highest contribution to the projection vector will come from the salient regions' features. In other words, when someone tries to describe the content of an image, he/she will focus more on the salient regions of the image. Interestingly, this coincides with the way people describe visual content of an image. For example, the reader may realize when he/she tries to describe an image, e.g. the image in the last row of Fig. 1, that the description will be probably made as follows: "A girl in red skirt and black shirt standing in front of some vegetation next to flowers". Such a description most likely starts with the most salient object/part of the image and less informative regions are mentioned later or not mentioned at all.
At this point, we would like to note that this interpretation is different from the 1-vs-all classification interpretation proposed in [50] where salient object is interpreted as a class and optimal features are pursued that best distinguish this class from others in the image. Our one-class based interpretation differentiates from this approach, as we interpret the whole image as a class (not only the salient region) and we claim that out of all regions in the image, salient regions are the ones that best describe the image content.
Here it should be noted that, based on the above discussion, diffusion methods can also be formulated as classification problems. This is further discussed in Appendix C.

III. EXPERIMENTAL RESULTS
To evaluate the performance of the proposed PSE method, we conducted extensive experiments in 5 widely used datasets, namely MSRA10K, DUTOMRON, ECSSD, JUDD and SED2. In order to evaluate different aspects of the obtained results, the performance is reported using multiple metrics, i.e. precision-recall curves, receiver operating characteristic curves, mean squared error, maximum F-measure and area under the ROC curve. Before giving a brief description of the datasets and the evaluation metrics, we first provide a few important implementation details.

A. Experimental set-up
The graph construction and weight affinity assignments follow those in [20]. Furthermore, the multiresolution approach and the corresponding superpixel granularities are exactly the same as in [20] in order to have a fair comparison with this method. The entries of the potential vector corresponding to the interior superpixels are set to zero, while the ones corresponding to boundary superpixels were set to a fixed value, empirically to one tenth of the maximum entry on the diagonal of the Laplacian matrix. We will show the robustness of the proposed method to this parameter later in this section.

B. Datasets
MSRA-10k dataset [11] is a superset of the popular ASD [31] dataset and contains 10k images. In each image, there is usually one large salient object with a high contrast to its surrounding. SED2 datasets [35] contain 100 images. Each image contains two salient objects. The saliency detection task in this dataset is relatively simple; however, the challenge is with the objects touching the boundaries. DUTOMRON dataset [14] is one of the largest datasets containing 5168 very challenging images. 25 participants were involved in selecting the images from a wider set of images containing 140k images, and manually labeling the ground truth. ECSSD dataset [12] contains 1000 images with semantically meaningful objects appearing in cluttered backgrounds.
Finally, JUDD dataset [42] contains 900 images and is the most challenging database with multiple objects and very high background clutter.

C. Evaluation Metrics
Precision is the ratio of the total number of true positives to the total number of detected samples. Recall is the ratio of the number of true positives to the number of true samples. For salient object detection, a true sample is a pixel in the ground-truth segmentation mask . A detected sample at a threshold is the number of nonzero elements in a saliency map thresholded with , denoted by .
F-measure is defined according to precision and recall values as follows: Although =1 is an intuitive selection for equal weighting of precision and recall values, in the salient object detection literature it is common to set = 0.3 in order to emphasize more on precision [37]. The reason behind this choice is the fact that it is relatively easier to achieve high recall than high precision. Therefore, in this work, we follow the recommendation in [37].
The receiver operating characteristics (ROC) is the curve plotting true positive rates as a function of false positive rates, denoted as and , respectively. The true positive rate is the same as Recall in (23) and the false positive rate is defined as the ratio of the total number of samples that are falsely classified as negative to the total number of negative samples: The area under the receiver operating characteristics curve, referred to as AUC-measure, gives a single scalar measure of performance, unlike ROC values at each threshold , and hence it is a more general measure of performance.
Precision-recall and ROC curves do not emphasize much on the smoothness within detected salient object regions. For example for a given threshold , if every pixel's saliency in the object region is larger than , and every background region is smaller than , this will yield perfect precision, recall and false positive rate. However, the saliency measures inside the object region can vary widely. In order to take this measure into account, the mean squared error is also used as follows:

D. Comparison with the state-of-the-art
We compare the proposed PSE method with the top-5 performing unsupervised techniques, according to a recent study [43], namely QCUT [20], RBD [15], ST [44], DSR [10] and MC [16]. DRFI [45] was also ranked as one of the top methods in the study; however, it is a supervised method and, hence, it is not included in our comparisons. The saliency maps for the above algorithms were downloaded from the website [30] related to the study in [43]. We further include comparisons with a recently proposed method GP [39]. The saliency maps for GP were extracted using the code provided by the authors.
In Fig. 2, we provide precision-recall curves for the state-of-the-art methods in the datasets mentioned above. One may quickly observe that although some methods such as ST perform well in relatively simpler datasets, such as SED2 and MSRA10k, they fail to provide a good performance in more complex datasets, such as JUDD and DutOmron. One of the top performing methods QCut tends to produce saliency maps that have relatively low precision on higher recalls when compared to other methods. This is evident from the quick fall of the curve in this region. Furthermore, due to its hard boundary background assumption in SED2 dataset, this method fails to preserve its leading performance. It is worth noting that the proposed PSE method is consistently one of the top two performing methods in precision-recall curves. PSE does not suffer from the sharp drop in precision at high recall as QCUT. Furthermore, it handles objects touching the image boundary as observed from the plots of SED2 dataset. In Table 1, we provide maximum measures for = 0.3. In three of the datasets (i.e. MSRA10k, ECSSD and SED2) PSE gives the top performance and on DutOmron and JUDD datasets, it achieves second best performance with a relatively small gap with the leading method.   [20], RBD [15], ST [44], DSR [10], MC [16] and GP [39]. Since their evaluation is based on different criteria, it is highly likely that one may observe quite different leaderboard in ROC curves and AUC measures than precision-recall curves and F-measures. A good method should perform well with respect to most if not all evaluation metrics. Fig. 3 provides ROC curves for the proposed method against the competing ones. The proposed method PSE is the top performing method in terms of ROC curves, except for SED2 dataset where PSE gives very high recall performance in low false positive rates. Note that one of the leading methods, in precision-recall curves, QCUT does not perform well with respect to ROC curves. The area under the curve (AUC) measures are provided in Table 2.  Table 2, we observe that PSE is leading in all datasets except for SED2 where it trails the leading method ST by a small margin. GP, DSR and ST also perform well in AUC measures (mostly 2 nd and 3 rd places); however, they are not as successful in precision-recall curves and F-measure.
Finally, we compare the performance of the compared methods in terms of mean squared errors in Table 3. PSE is the top performing method in ECSSD, JUDD and SED2 databases and the second in MSRA10k and DutOmron. We can conclude that PSE consistently results in leading performance across a wide range of evaluation measures and it is always within the top two.   [20], RBD [15], ST [44], DSR [10], MC [16] and GP [39]. (Top row, from left to right) Curves for datasets MSRA10k, DUTOMRON, ECSSD. (Bottom row, from left to right) Curves for datasets JUDD and SED2. Finally, the average run times for the compared methods are provided in Table 5. Run times denoted by asterisk are calculated on a PC with Intel i7-3740QM CPU @2.70 GHz. Since we do not have access to some of the methods, other run times are copied from the study in [43].
We can see that the run time in our PC is slightly less than the one reported in [43] for QCUT. Hence, it is safe to compare the results accordingly. From Table 5, we can observe that PSE is comparable to the fastest methods and much faster than ST and DSR. Given the leading performance of PSE, slight computational burden over the fastest methods does not prevent favoring our method over others.

E. Robustness with respect to Boundary Prior
Next, we will investigate empirically the robustness performance of PSE against variations in the initial boundary potential assignment. As previously noted, we have set a unary potential value on the boundaries of the image to a value proportional to the maximum entry in the diagonal of the Laplacian matrix. Let us denote this value with q.
In Fig. 4, we observe the changes on the precision and recall curves and the receiver operating curves as q changes over a wide range (0,001-10). We can safely say that precision-recall curves are more robust to variations in q than ROC curves. For q values greater than 0.01, one can still observe that ROC curves are also quite robust to this parameter. We have conducted tests on two very different datasets, i.e. ECSSD and SED2. As stated in [43], ECSSD is a dataset where objects are closest to the center and least touching the boundaries. On the other hand, SED2 is a dataset where objects are farthest from the center and most touching the boundaries. Indeed, we observe slightly better precision-recall performance for higher q for ECSSD and lower q for SED2.
However, for both datasets, slightly higher values of q are preferable for ROC curves. Higher q values perform better in terms of precision since boundaries are strongly suppressed; however, recall may suffer if the object is touching the boundary. On the other hand, lower q values may lower the precision, but will improve the recall since PSE in this case does not rely too much on the boundary prior. In our experiments, we observed that it is favorable to choose q = 0.1 as a moderate value to cover both cases. This value is used in all experiments and all datasets, although better performance than reported in this study may result from tuning this parameter for each dataset. To see the justification more clearly, we also provide the MSE, AUC and maximum ( = 0.3) measures for all q values for ECSSD dataset in Table 6 and for SED2 dataset in Table 7. For the former dataset, the performances for all measures increase as q increases; however, the improvements are not that significant beyond q = 0.1.
For the latter dataset, we observe a reduced performance for MSE as q increases; however, for AUC and measure, the best performance results from moderate values of q. , . , . , .

F. A More Detailed Comparison with GP
As previously explained, PSE can also be interpreted as a diffusion problem, where a special diffusion matrix is used and the seed vector contains entries that are constant and equal to 1 for each region. Therefore, besides the extensive performance evaluation given above, we provide a more detailed comparison with the most recent diffusion method GP [39]. First, we analyze the effect of the affinity matrix on the performance of GP using our affinity matrix. Next we investigate the effectiveness of the seed vector used in [39] compared to a constant 1 seed vector. We only provide precision-recall curves, since the performance with respect to other metrics are quite similar. As we can observe from Fig. 5, GP is heavily dependent on the affinity matrix that is used, as we observe a very sharp performance fall when using our affinity matrix. On the other hand, a minor difference is noticed in performance when using the seed vector s and a seed vector of 1. According to our observations, these effects are > REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 21 mainly due to the graph structure used in [39], where each boundary region is connected to all other boundary regions, making it difficult to assign a boundary region as a salient region. Therefore, assigning zero values to the seed vector to suppress boundary regions is not effective. On the other hand, other graph structures, such as the one used in the proposed method, result in total failure of GP even when using the pre-defined seed vector s.

IV. CONCLUSION
In this paper, we proposed a novel unsupervised salient object detection method based on a probabilistic framework. This method was shown to have several interpretations, such as spectral foreground detection, diffusion-based salient object detection and one-class classification. Such a general framework enjoys a global optimal solution of a criterion that integrates boundary connectivity saliency cue and smoothness constraints. Moreover, based on its interpretations, we showed that it also provides an approximation of the global optimum of another criterion that inherently exploits other saliency cues: local/global contrast and large area cue. Extensive experimental evaluations demonstrated that the proposed method can reach leading performance among the state-of-the-art unsupervised salient object detection methods in a wide variety of datasets with several evaluation criteria.

Fig. 5
Precision-recall curves for ECSSD dataset for PSE, GP, GP with our affinity matrix and GP with seed vector of 1.

APPENDIX A PROBABILISTIC ANALYSIS OF DIFFUSION METHODS
Here, we provide a probabilistic interpretation of diffusion-based salient object detection methods. Based on this interpretation, we explain why it is expected that PSE is able to produce better saliency maps, when compared to such methods.
Similar to the approach in section II, first let us define the prior probability of selecting a state as the salient region (x= ), and an observation random variable s that (x= )is dependent on. An example of this observation can be another event of selecting a salient region which can be, for example, another saliency detection method. The -normalized saliency result of this supporting model can be denoted as (s= ) . The sample space of both random variables x and s is the same and equal to the pixels/regions in the image. This is why samples for both events are defined over the image regions . Then, by Bayes theorem, one can write the following: The conditional probability x= |s= is most informative when = , since this means that the probability of selecting image region as a salient one given that the outcome of another salient region selection procedure also selected region as the salient region. We represent (x= |s= )as the element of the vector , and (s= )as the element of vector . Based on these, we can formulate a new optimization problem, where the goal is to find an optimal satisfying a similar minimization to that in (1), as follows: The difference between (28) and (1) is two-fold. First, (28) does not include the background penalization term and second, the constraints are different. It is straightforward to show that ≤1, since = (x= |s= )corresponds to some portion of the conditional probability. Moreover, the global minimum of (28) cannot be directly obtained as ( − ) , since − is singular. However, one can find an approximate solution by adding a small noise term to the diagonal of the Laplacian as follows: * = ( − + ) . (29) The result in (29) is a regularized solution of (28) and is similar to the approach in [14] as claimed by [39].
The above analysis gives us the formulation of a diffusion based method, where the diffusion matrix is the inverse Laplacian matrix. An important observation related to the Bayesian interpretation of diffusion-based methods is that these methods are interested in the conditional probability = (x= |s= ) and discard information about = x= | s= when ≠ . Based on this, we can conclude that this result is dependent on the observation s that is interpreted as another salient region selection event. On the other hand, by the formulation of Eq. (1), PSE does not include such dependency to a pre-estimated saliency map, it rather suppresses confident background regions. This is a more trustable approach since background initialization is much easier than foreground estimation. Furthermore, approaches such as selecting the seed vector as 0 on the image boundaries and 1 in the foreground to use boundary connectivity cue results in noisy saliency maps, since all interior regions are given the same initial saliency confidence.
Above, we have presented a probabilistic interpretation for a specific diffusion based method [14]. We can give this interpretation for other diffusion based methods as well. For example let us consider the work presented in [40], where a manifold ranking method was proposed that exploits the manifold of the given graph structure. In [41], it was shown that this manifold ranking corresponds to the following unconstrained minimization: In (30), is the result of the ranking query and is the initial confidence. The optimal solution is obtained by: Graph based manifold ranking [14], which is yet another diffusion based method, can also be formulated in our Bayesian interpretation as follows: The global optimal solution * is exactly the same as * except for the normalization term , instead we have a term related to both and which is ensured by the constraint = . Indeed, (30) is a special case of (32), where we restrict the joint probability of x and s in the region of interest to ensure the normalization value in (31). One can also show that and is proportional. A large value also ensures a large value, which means that the confidence on the observation s is large. In the extreme case, i.e. when =1, events x and s correspond to exactly same random variable.
Comparing There are two shortcomings of this approach in terms of saliency: first the dependency on the parameter , second similarity enforcement based on support regions. Selecting an optimal value is an open problem. However, a bigger problem is the effect of similarity enforcement based on support regions instead of the regions themselves. This results in different labeling of parts of regions closer to object edges and the ones in the interior object region.
We have given a Bayesian interpretation of diffusion based methods and explained their shortcomings based on this approach.
These examples can be populated by giving other optimization problems resulting in different diffusion matrices. However, due to lack of space we omit giving more examples. As a result of our investigation both experimentally and theoretically, we can state that these methods require a good initialization. Therefore diffusion based salient object methods [16], [14], [39] require a good post-processing technique and special graph designs to produce an accurate saliency map. On the other hand, PSE does not require any foreground confidence nor does it require any refining procedures to obtain an accurate saliency map.
The difference between (1) and (33) is the fact that the former penalizes the distance between estimated probabilities whereas the latter penalizes the distance between the square-root of the probabilities. We have already observed that PSE generates much more accurate saliency maps compared to QCut, especially in terms of high recall in this study. For symmetric affinity matrices and a non-zero prior , we have justified this performance difference by the relation of both methods via diffusion maps [38].
We can also come to the same conclusion observing that (33) may produce much sharper saliency maps compared to (1). Since the probability values are smaller than (or equal to) 1, minimizing the distance between the square-root of the probabilities would result in significant changes in saliency maps between the regions with small contrast. However, (1) results into smoother regions, ensuring a higher recall.

APPENDIX C DIFFUSION METHODS AS CLASSIFICATION METHODS
As has been described in Subsection II.D, PSE can be interpreted as a one-class classification problem, trying to model the image at hand. Based on our observation in Subsection II.A related to the similarity of PSE and diffusion methods, we can also cast such methods as classification methods. However, since they usually exploit a binary seed vector , which might be the output of another saliency detection method, they solve a two-class problem. In the case where the exploited seed vector contains real values, diffusion methods solve a regression model trying to map the image region's features to the values of . In other words, they are trying to find a projection vector that optimally regresses the image features to the seed vector, which might be an output of another saliency detection method or some heuristics based initialization. In both cases, it is clear that their output * will be dependent on .