Adrien Chan-Hon-Tong

Stéphane Herbin

Practical scheduling of computer vision functions

published or not. The documents may come

Introduction

Computer vision focus on developing routines which solve computer vision tasks like deblurring [START_REF] Shan | High-quality motion deblurring from a single image[END_REF], registration [START_REF] Bruce D Lucas | An iterative image registration technique with an application to stereo vision[END_REF], segmentation [START_REF] Yu | A survey on evaluation methods for image segmentation[END_REF], classification [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF], pixelwise classification [START_REF] Shotton | Textonboost: Joint appearance, shape and context modeling for multi-class object recognition and segmentation[END_REF], object detection [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF].

However, in computer vision, there exist multiple non dominated routines designed for a same task: for image classification, there exist classifiers with better quality than the state of the art but also classifiers faster with almost state of the art quality.

For example, even if deep learning classifiers (like alexnet [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]) have brought an important quality increasing on classic datasets (eg. [START_REF] Russakovsky | Imagenet large scale visual recognition challenge[END_REF]), its do not completely dominated classifier state of the art because deep learning classifiers have classically a running time greater by one or two orders of magnitude than older classifiers (eg. HoG+SVM [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF], boosting [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF], DPM [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF]). Now, let wonder about how to design system which should classify batches of N images in T seconds using black box classifiers. This leads to a scheduling problem i.e. mapping effectors on resources across time to perform tasks. Such kind of problem is classic in discrete optimisation.

Precisely, let assume that the system has C available resources and can rely on K classifiers each associated to an overall quality q1, ..., qK , a speed s1, ..., sK (speed is approximated as constant), and a resource consumption c1, ..., cK . In practice, one could take a look at the state of the art and select the classic classifier from the K which best fit to the problem. But from scheduling perspective, this approach is clearly not the one which maximizes the output quality -unless if one day a new classifiers would dominated all previous ones (both in quality and speed).

A little step toward such maximization is done by the following model: let the number of images x k processed by the classifier k, as batch should 1 be processed in T seconds, each classifier should process this own subbatch in less than T seconds (leading to ∀k, s k x k ≤ T ) -in addition each image should be processed ( k x k = N ) -finally, if an classifier is used (x k = 0) then it uses some resources. So forgetting that one classifier could start after than on other have stopped, the value x k are the solution of the following integer linear program: max

x 1 ,...,x K ∈N k q k x k sc : ∀k, s k x k ≤ T k x k = N k c k (x k = 0) ≤ C
Clearly, even if this set of inequalities may be NP-hard, it is in the format of well studied family of discrete optimisation problem and can be -at least -easily approximated. But, the reality is much more harder because this set of inequalities does not take into account that one can apply a classifier on a image and react to the output of this classifier for example by using an other classifier only under some circumstances. More precisely, let suppose we are talking about binaries classification (images are either positive (e.g. target) or negative (e.g. background)) and assume that all classifiers have almost the same behaviour on positive but have very different behaviour on negative i.e. the faster the higher number of false alarms. It could still be interesting to use a fast classifier which will produce a lot of false alarms as soon as we could filter these false alarms using a slower classifier -and this is completely not taken into account by the previous model. By the way, such cascaded strategy is the heart of [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF] which contributes to trigger the deep learning revolution by offering an algorithmic solution to the deep learning slowness using the box proposal paradigm -against the sliding windows one -in object detection.

To return to our scheduling problem, modelling the possibility to form cascaded decision would lead to a very challenging scheduling problem even if classifiers were predictable objects (stochastic programming with free number of recourse steps). In addition, to be very hard, this new kind of scheduling is not well studied and computing the optimal allocation would probably takes more time than the allowed time T . But worse -classifiers are not predictable: the number of false alarms produced by a classifier can significantly differ from validation to test set. Thus, the behaviour of a given cascaded allocation is even not calculable (independently from the data) whereas cascaded strategies are known to belong to good strategies.

So to summarize, we take one of the simplest computer vision problem and the derived scheduling problem is yet intractable.

So, we learn from this introduction that classical scheduling literature is not well compatible with scheduling in computer vision context.

However, we state that offering scheduler of computer vision routines (like classifiers) may be useful not for the sake of performance but to make easier the development of robotic system embedding computer vision. Such scheduler even if producing output with quality slightly under state of the art could be useful to separate computer vision from integration implementation. This would allow easy prototyping, and, could boost the apparition of robotic platform embedding a large variety of computer vision functions.

For example, building a computer vision system where image processing produces a feed back on image acquisition (e.g. [START_REF] Paillet | Imm-based tracking and latency control with off-theshelf ip ptz camera[END_REF] is still challenging as one need to deal with both classification/detection task but also camera motion controlling/latency handling/communication managing. Another example is building a time constraint batch classification system able to make few queries to an human operator (much slower with an unpredictable reaction time but with almost perfect quality) [START_REF] Russakovsky | Best of both worlds: human-machine collaboration for object annotation[END_REF].

We argue that robotic community heavily relies on middleware like ROS [START_REF] Quigley | Ros: an open-source robot operating system[END_REF] or YARP [START_REF] Metta | Yarp: yet another robot platform[END_REF] very useful for easy prototyping and large project even if such middleware obviously introduces computation overhead -this is not that far from using scheduler for black box functions.

Thus, we believe that this work about practical scheduling of computer vision functions is relevant for robotic communities (and maybe computer vision one) in a (close) way ROS and YARP are.

In the following, we first describe related works in section 2. Then, in section 3, we describe a simple but effective scheduler for the time constraint batch classification problem under real setting both in term of hardware target (hybrid CPU GPU) and in term of classifiers (e.g. with Alexnet). The relevancy of this scheduler is validated on experiment on real computer vision dataset (in section 4), before conclusion in section 5.

Related works

The task of selecting combinations of actions to optimize a process is a generic task that overlaps at least three well studied fields: discrete optimisation [START_REF] Ouelhadj | A survey of dynamic scheduling in manufacturing systems[END_REF][START_REF] Ronald L Graham | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF], path planing [START_REF] Lamiraux | Smooth path planning for car-like robots[END_REF][START_REF] Marti | Path planning for robots by stochastic optimization methods[END_REF], and Markov decision process [START_REF] Bellman | A markovian decision process[END_REF][START_REF] Song | Optimal electricity supply bidding by markov decision process[END_REF].

In this paper, we want to apply scheduling to computer vision functions. However, computer vision is an exigent field in resources consumption: for example, in automatic car driving, computer vision system should typically process an HD image each 33ms whereas 1 hour of uncompressed HD video is around 1To. So both to size of the data and the dynamic is really high. In addition, computer vision is a data driven field where effect of an computer vision functions dramatically varies depending on data making impossible to precompute computer vision function effects.

Thus, there is a crucial difference between classical scheduling context and our context: here, time taken to compute the scheduling is required to be insignificant regarding action duration (which is yet very low) and can not be precomputed.

In discrete optimization, the goal is often to precompute an allocation of the resources. The ability to react to the effect of an action that could have been different from what was expected is handled in particular by stochastic programming. However, stochastic programming is mainly about the ability to select the first order variables before some random input will be known, taking into account the fact that there will be second order variables (sometimes called recourse variables) to set up after (e.g. [START_REF] Ferrero | A dynamic programming two-stage algorithm for long-term hydrothermal scheduling of multireservoir systems[END_REF]). We found little literature about the relevancy of using stochastic programming on problem with very high dynamic (like having to schedule the processing of 250000 jobs in less than 200ms).

There are also difference with path planning. In path planning, optimisation is usually considered at trajectory level while, in this paper, optimisation is considered at a dynamic level which has the same order of magnitude than engine controllers. Clearly, the voltages associated to engine controllers is not usually scheduled (but often handled by other kinds of methods including old school proportional-integral-derivative PID method). There exists example (like [START_REF] Van Den | Lqg-mp: Optimized path planning for robots with motion uncertainty and imperfect state information[END_REF]) of path planning optimisation at engine controller level. However, this literature is relatively restricted. And, even if scheduling was relevant on this time scale: engine controllers are much more regular than computer vision function. Off course, even with the knowledge of the applied voltage, no one can perfectly predict the speed of an electric engine as there is always uncertainty. However, this uncertainty is relevantly modelled by some smooth distribution and is moderately low. This is completely not the case for computer vision functions (performance can significantly differ from validation set to test set), and thus, there is a big difference between these two contexts.

These consideration also stand for Markov decision process. In Markov decision process, applying an action a from a state s is often simply getting the value T [a][s] of the matrix T . Thus, the action duration is insignificant regarding the time of optimisation which is the opposite of our context. Also, even if Markov decision process can be extended with irregular actions, the framework is more relevant for deterministic or probabilistic actions. This is especially true for large state system. Thus, on our context, there is little relevancy to use classical method like Q-learning [START_REF] Richard | Reinforcement learning: An introduction[END_REF].

For all these reasons, there are only very few papers applying scheduling methods to computer vision context. From these papers, the closer to our work are (in our opinion) [START_REF] Trapeznikov | Supervised sequential classification under budget constraints[END_REF] and [START_REF] Russakovsky | Best of both worlds: human-machine collaboration for object annotation[END_REF].

In [START_REF] Trapeznikov | Supervised sequential classification under budget constraints[END_REF], the considered system is a predefined cascade of K classifiers. Each new can either be classified by the classifier k or be considered as suspicious and given to the classifier k + 1. As classifier K cost much more than classifier 1, the trade off is to tune the system to achieve high quality at low cost. In addition to provide framework to deal with this trade off problem, [START_REF] Trapeznikov | Supervised sequential classification under budget constraints[END_REF] use Markov decision process to prove that a simultaneous training of all classifiers taking into account the cascaded structure of the system is possible.

This work is thus close to our, however, our goal is to dynamically schedule classifier jobs -considering classifiers as black box. In other work, we are trying to automatically find the correct cascaded structure while [START_REF] Trapeznikov | Supervised sequential classification under budget constraints[END_REF] tries to tune it. So we are not scheduling at the same level.

Finally the closest work, in our opinion is [START_REF] Russakovsky | Best of both worlds: human-machine collaboration for object annotation[END_REF]. In [START_REF] Russakovsky | Best of both worlds: human-machine collaboration for object annotation[END_REF], dense application of deep learning classifier is precomputed on a batch of images. Then the goal is to interact with an human operator to extract from this dense precomputed values, the set of object present in the batch of images. The algorithm to as input the cost of several human action (drawing a bounding box, tell if a bounding box is correctly located, tell is there is an object in the image, tell is there is a certain kind of object in the image ...) and a trade off criterion between the cost of human annotation and the quality of the the set of extracted boxes. The extremal cases are complete manual annotation is human cost is 0 and complete automatic annotation is human cost is infinite. Between the two extremal case, the system tries to use efficiently the human resources to improve purely automatic annotation.

Clearly, if we add human interaction is the set of computer vision functions, then scheduling the interaction with a human is part of what the scheduler would do. So [START_REF] Russakovsky | Best of both worlds: human-machine collaboration for object annotation[END_REF] is close to a particular case of this work. The main difference is that we do not precompute computer vision values instead we are doing it online (i.e. on the fly) while reacting to the previous computation.

However, some Markov decision process tools are shared between [21] and our work. In particular, we also use look ahead planning (LAP). In [START_REF] Russakovsky | Best of both worlds: human-machine collaboration for object annotation[END_REF], LAP with temporal horizon of 2 is used to schedule the interaction with the user. In this work, a LAP in the expected word with large temporal horizon is used instead (this will detailed just after) -but the same LAP is use in both case.

3 Offered scheduling framework

Basic assumption

We describe in this section our framework for scheduling computer vision classifiers to tackle the toy problem of time constraint image classification. The system should classifies a batch of N images in T seconds using K black box binary classifiers whose expected quality q1, ..., qK , speed s1, ..., sK and resource consumption c1, ..., cK are known on a hardware platform with C available resources.

First, we assume that default decision on unprocessed images is to consider it as positive. Then, we assume all classifiers have a common and relatively high recall: it means that classifiers have almost the same behaviour on positive images. However, we allow large variability in speed, resource consumption and precision (which is linked to false alarms rate: the better is an classifier the lower there are false alarms as recall is fixed).

Then, at each moment, the state of the system is the current vector of label (one for each images) and the vector of confidence (one value indicating the confidence onto the label).

Each classifier is encapsulated into an elementary action. Applying an elementary action on a state consists in: sorting image per confidence, extracting some of the ones with less confidence, classifying each image and re-inserting its on the state. The number of images extracted by an elementary action depends on the speed of the underlying classifier.

More precisely, we select a step duration and each elementary action should have this duration. Thus, if the underlying classifier has speed s (in images per second) and the step duration is δ (in second) than the number of image processed by the elementary action is s × δ.

The confidence given to each image is the precision of the most precise classifier that have classified it (which can only increase -we do not allow classifier with lower precision than the confidence to handle an image).

A set of elementary actions which can be run simultaneously (considering the set of available resources) is an action. A crucial point is that when we apply an action in a state, all elementary action select the images that its will handle sequentially but images processing is done in parallel (re-inserting is done sequentially too). So into a same action elementary actions will can not process a common image.

To reduce the number of possible action, we consider non dominated action only: if action ijk is possible than it is no interesting to consider action ij (i,j,k being 3 elementary actions). Also, permutation into elementary action are not relevant so action ijk is the same as action ikj or kij. Contrariwise, all classifiers can be used multiple time -this increase the number of possible actions but it is crucial to be relevant. In other words, if i and j only need 1 CPU than iiiii, iiiij, iiijj, iijjj, ijjjj, jjjjj are allowed actions.

Look ahead planning

Like [START_REF] Russakovsky | Best of both worlds: human-machine collaboration for object annotation[END_REF], we rely on look ahead planning (LAP) to schedule actions.

So the global steps of the system are:

• select/read the duration step δ

• encapsulate each classifier into an elementary actions with number of processed images s × δ where s is classifier speed

• compute A the set of multi-set of elementary actions which are allowed seeing C, non dominated, permutation less

• initialize state

• do T δ step of LAP from state Let recall the core of the LAP: the LAP is decomposed in two steps

• to explore the path from a starting point to compute the reachable score

• to apply the first action from the best path So let assume there is 3 actions a, b and let note s :: a to design the state resulting of the application of a from state s then the LAP on temporal horizon of 2 consists in computing s :: a :: a, s :: a :: b, s :: b :: a, s :: b :: b to find if starting by a or b lead to better score -then LAP consists to apply to s the action leading to best score and loop again. The pseudo code is described in figure 1.

Notice that we have introduced the concept of score of a state without describing it. Here, we use the expected expected precision as state score. This computation is done using the classifier calibration: the expected precision is simply the average on the images classified as positive of the precision of the classifier used on. The use of the precision is relevant as all classifier have a common recall. Now, there is two problems with this version of LAP:

LAP(A, state, n) for t=0 to n exploration = [state] explore(exploration,A, n-t) a = argmax(exploration); state = apply a on state; return state; Figure 1: the pseudo code of the look ahead planning

• we can not explore all path as there is α β paths where α is the number of actions and β the temporal horizon of the optimisation

• we could not explore at all at this point because applying an action onto a state to know the resulting state is exactly what we do not want to do: the computational time should overwhelmingly be used to apply action to state and not to select the next action.

For the first problem, we use like in [START_REF] Russakovsky | Best of both worlds: human-machine collaboration for object annotation[END_REF] a greedy pruning of the exploration to maintain a low computational volume while taking advantage of long term information.

For the second problem, we do not need exact state computation: we only need a coarse estimation of what would be the state after the application of the action. For this purpose, we introduce virtual state.

Action selection

We offer to simulate the application of computer vision functions on virtual representation of the state.

In particular, if the real state is the vector of label/confidence, a virtual representation is just the distribution of label/confidence. Because, using the calibration of the algorithm, we can estimate the resulting distribution of the application of a classifier without performing a real application.

For example, if the state is composed of α negative images and β positives ones associated with a precision of λ, then applying a classifier of precision µ > λ on γ < β positive images leads on average to α + γ -γλ µ negatives and β -γ + γλ µ positives (β -γ with precision λ and γλ µ with precision µ). These equation comes from the conservation of positive and the equation positives = estimate positive × precision.

Using this trick of virtual state, the selection of action is pretty close to Markov decision process framework. So, we perform a simple path exploration like in [START_REF] Russakovsky | Best of both worlds: human-machine collaboration for object annotation[END_REF] (with the same greedy pruning) to estimate the reachable score given a state (real or virtual).

For this point, one could think about analytic model of the elementary action which could lead to a smoother optimisation than LAP. However, we want to stress that the application of a classifier to a virtual state is globally regular but not at critical point (for example when γ > β > 0 in our example). But, the emphasis of the optimisation is mostly to navigate between these critical points. So, we feel that simple exploration is a good way to select action. The pseudo code of the exploration is described in 2. Now, we have completely described our scheduler. The main originality is to use virtual state in order to fall into LAP framework.

Experiments

Scenarios

In order to provide realistic condition to evaluate the scheduler, we transform an object detection problem into a batch classification one using sliding window framework.

Let imagine police forces searching for a threat in a city. Large aerial images are acquired, and in the same time, semantic description of the threat is acquired from an other source (e.g. phone conversation). Scanning the entire city by hand is too time consuming thus there is an interest perform pre detection using a computer vision toolbox. Now, the computer vision toolbox contains many functions with different tuning. Building a relevant computer vision pipeline for the given task on the fly could be unrealistic as it requires both operational and computer vision expert knowledge. Thus, there is an interest for a system which is able to schedule functions from the toolbox from an expression of the threat into the toolbox vocabulary, even if a specific state of the art function could have been produced a better output.

Thus, a realistic specification for our system is the ability to process the area of a standard city 50km in an hour on standard hardware : 6 intel7 CPU, 6Go of RAM and 1 GeForce GTX 750.

Data

We choose to use the 2015 IEEE GRSS Data Fusion Contest to perform our experiments. This dataset (called grss dfc 2015 in this article) is composed of 6 large size (10000x10000 pixels) remote sensing ortho-images with resolution of around 5cm (only RGB image are used in this experiment). Each grss dfc 2015 image (covering 500m) should be processed in 36 seconds in order to respect the time constraint.

A manual semantic labelling has been made by [START_REF] Lagrange | Benchmarking classification of earthobservation data: from learning explicit features to convolutional networks[END_REF]. We adopt a 128x128p mono scale sliding window framework with spatial displacement of 20 pixels of the window. So a 10000x10000p image leads to 250000 128x128p images to processes in 36s: this is almost 2 order of magnitude the number of 128x128 images that the AlexNet convolutional neural network can processes on 36s a GeForce GTX 750 making relevant the possibility to combine different classifiers to process more 128x128p images (even if these other classifier are less accurate than Alexnet).

We split the dataset in 3 sets (train/val/test) of 2 images. Each computer vision function is calibrated on the validation set (after a training on train set) in order to obtain statical characteristics of each function. The scheduler considers each computer vision functions like a black box only coming with a calibration report. The complete system (scheduler + functions) is tested on the test set (composed of the 27032011 315140 56865 and 27032011 315135 56865 images).

Computer vision library

The computer vision classifiers considered for the experiment are For each classifier, we select the threshold leading to 90% of recall. Each classifier even (deep learning) is terminated by a SVM (see [START_REF] Chapelle | Support vector machines for histogram-based image classification[END_REF] as an example of paper on this field). The tables 1 present performances of all classifier and statistic extracted from the auxiliary data. These tables are the only function descriptions available to the scheduler. Here, all classifiers are calibrated on validation set to have a common recall of 90%, thus precision should be the only mutable value. This is however not the case due to interaction in the cascaded decision: baselines still have around 90% of recall while scheduler has around 65% of recall. However this loss of recall is no very significant regarding the impressive increase of precision. All system terminates in the allowed duration -time used by the scheduling process in addition to effective computer vision time is less than 5%.

Table 2: Performance of our system (scheduler + classifiers) and baselines on the grss dfc 2015 dataset.

Results

We run both our scheduler and several baseline with this experiment setting. In our opinion, all elements of this experiment are realistic: data are real work remote sensing images, hardware target (C) is a standard hybrid CPU GPU environment, the allowed time (T ) seems representative (1 hour for classifying a city) and considered classifiers contains in particular outdated HoG and state of the art Alexnet. In all experiment, one CPU is allocated to the image server (so the targeted system behaves like having 5 CPU instead of 6). The considered baselines are:

• the better available combination: mapping one GPU and one CPU onto alexnet and one HoG 128x128p on each other CPU

• the faster available combination: mapping each CPU to HoG 32x32

• the better combination respecting the constraint of processing almost all 128x128p images: here, this leads to map all CPU on HoG 64x64p

The results are summarized in table 2. Some results are not very surprising:

• using only the better available combination leads to process only 23% of the 128x128p images (all non processed 128x128p images is assumed to be classified as positive) naturally resulting in a huge amount of false alarm.

• using only the faster combination leads to process all the 128x128p images in a very small amount of time (3 times less than the allowed duration) but each 128x128p image has been classified with a weak classifier also leading to a huge amount of false positive Low results of the middle baseline are more interesting. This middle baseline has some quality on the paper: it is simple to implement (only one classifier), it takes into account the tradeoff between good individual classification and good global coverage. However, in this experiment, the middle classifier is nearly the only that is never used: the scheduler almost select either very fast either very good classifiers but rarely the middle one.

The global output of the scheduler is incomparably better than baseline ones in F1 measure (baseline keep a very high recall around 90% but have dramatically low precision while our system offer relevant precision losing only 25% of recall). It is even better that one could expect seen the calibration report (table 1). This could be explained by the difference between calibration which is done classifier per classifier and the scheduling were boxes are finally classified by multiples classifiers. In other words, the considered classifiers have some complementarity that are freely exploited by the scheduler. This complementarity could have been calibrated by building mutual calibration: evaluation of the performances of the classifier A on classifier B output. However, this mutual calibration may lead to combinatorial explosion and lack of examples induced bias, and more importantly can not be trivially exploited: should the scheduler remember which classifier has been applied on each 128x128p images ? The answer is that such memory is dramatically expensive both physically in memory consumption but also because when looking for the next combination of classifier to apply, the scheduler has to deal with a lot of situation instead of just a expected quality on each images.

Even if in this particular dataset, our scheduler completely outperforms all baselines (by 40% of F1 measure), we want to stress that our goal is not to improve performances of the computer vision state of the art, our goal is to offer a simple yet effective scheduling framework for computer vision functions and especially classifiers. Thus, in our opinion, the main result of this experiment is just that our framework is relevant for scheduling classifier of this dataset.

Conclusion

The goal of this paper is to make a step toward scheduler for help the integration of large computer vision library into complex robotic system. For make this step, we chose a scheduling problem derived of one the simplest computer vision: time constraint batch classification. We describe a scheduling framework for this problem and apply it on car detection on real word computer vision dataset with realistic time constrains, target hardware and computer vision routines. The results of this experiment is that scheduler goes further than expected by achieving state of the art result instead of just offering sufficiently good result to be relevant for prototyping/integrating needs.

This beyond-our-plan success will lead to conduct future works. First, we will tackle semi-automated on-the-fly computer pipeline design (where user just set the cost function and scheduler apply the different classifiers to produces automatically a sufficiently good result ). Then, we will tackle feedback loop between computer vision functions and camera devices and engine on moving robotic platform.

Figure 2 :

 2 Figure 2: Greedy routine exploration of LAP.

•

  128x128p HoG • 64x64p HoG (downscaling the original 128x128p image) • 32x32p HoG • 128x128p Lenet [13] • 64x64p Lenet • 227x227p AlexNet (scaling the original 128x128p image)

Table 1 :

 1 Performance and speed of the classifiers on the validation test.

	classifier	precision speed
	alexnet	10%	380
	lenet 128x128p	3%	1088
	lenet 64x64p	2%	5739
	hog 128x128p	1%	1580
	hog 64x64p	0.7%	6185
	hog 32x32p	0.1%	14229
	All classifiers have a common recall of 90% and speed is measured in 128x128p
	images per second. We use caffe [8] implementation with cudnn3 to enforce
	state of the art speed.


Paras Patel

Manish Patel

Sankalchand Patel

Tumor Detection using Particle Swarm Optimization to Initialize Fuzzy C-Means

Keywords: Segmentation, Particle Swarm Optimization, Fuzzy C-Means, Magnetic Resonance Imaging, Natural Computing

Image processing techniques are extensively used in different medical fields for earlier detection and treatment stages, where time factor is more important to find abnormality issues in target images in several tumors. Now a days tumor is discovered at advanced stages with the help of Magnetic Resonance Imaging (MRI).This paper proposes an approach which combines the Particle Swarm Optimization (PSO) techniques and Fuzzy C-Means (FCM) algorithm to perform image segmentation on Magnetic Resonance Imaging (MRI).The FCM algorithm has some limitations that it requires initialization of cluster centroids and the number of cluster. In this work, the PSO techniques is applied to the MRI medical images for the purpose of initialization of cluster centroids, which could overcome the requirement of manual initialization of FCM algorithm. Natural Computing (NC) is a novel approach to solve real life problems inspired in the life itself. A diversity of algorithms had been proposed such as evolutionary techniques and particle swarm optimization (PSO). This approach, together with fuzzy c means (FCM), give powerful tools in a diversity of problems of optimization, classification, data analysis and clustering.

I. INTRODUCTION

Image processing is one of the swift growing areas in signal processing. Image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or a set of characteristics or parameters related to the image. Most image-processing techniques involve treating the image as a two dimensional signal and applying standard signal-processing techniques to it [START_REF] Gonzalez | Digital Image Processing[END_REF].Normally, the anatomy of brain tumor can be examined by MRI scan or CT scan. MRI is a one type of scanning device, which use magnetic field and radio waves [START_REF] Zhao Zaixin | Neighbourhood Weighted Fuzzy C-Means Clustering Algorithm For Image Segmentation[END_REF]. It is also use computer to create images of the brain on film. Brain tumors affect the normal brain activity. So accurate detection of tumor is important for human and increase the lifetime of the 1 to 2 years [START_REF] Mokhled | Lung Cancer Detection Using Image Processing Techniques[END_REF]. In medical imaging, an image is captured, digitized and processed for doing segmentation and for extracting important information [START_REF] Rakesh1 | Image Segmentation And Detection Of Tumor Objects In MR Brain Images Using FUZZY C-MEANS (FCM) Algorithm[END_REF]. Fuzzy C-Means is the most popular algorithm for soft clustering [START_REF] Gonzalez | Digital Image Processing[END_REF].It has been widely used to make good separated clusters. The FCM is based on the minimization of an objective function and iterations through update the membership of degrees and centroids of cluster.FCM is frequently used with the image segmentation because it can retain more images information than the hard clustering algorithm [START_REF] Gonzalez | Digital Image Processing[END_REF].Although FCM algorithm works better than the hard clustering algorithm, but in FCM also unavoidable defects that cluster centroids and the number of cluster should not be decide in advance [START_REF] Guo | Color Image Segmentation Based On Decision-TheoreticRough Set Model And Fuzzy C-Means Algorithm[END_REF] to overcome the drawbacks of FCM in this paper we mainly focus on how to decide the cluster centroids and the number of cluster for better clustering. In this paper suggested an approach which combines the Particle Swarm Optimization (PSO) techniques and Fuzzy C-Means (FCM) algorithm to perform image segmentation .on Magnetic Resonance Imaging (MRI). Natural Computing (NC) is a novel approach to solve real life problems inspired in the life itself. A diversity of algorithms had been proposed such as evolutionary techniques, and particle swarm optimization (PSO) [START_REF] Naffouti | An Additive Image Watermarking Method Based On Particle Swarm Optimization[END_REF].Particle Swarm Optimization (PSO) technique developed by Kenny and Eberhart in 1995 [START_REF] Kennedy | Particle Swarm Optimization[END_REF].In Particle Swarm Optimization, simple software agents, called particles moves in the search space of an optimization problem. This approach,together with Fuzzy C-Means (FCM), give powerful tools in a diversity of problems of optimization, classification, data analysis and clustering [START_REF] Mokhled | Lung Cancer Detection Using Image Processing Techniques[END_REF]. On the whole, for good segmentation we use the Particle Swarm Optimization technique to trigger FCM For good initialization. we can randomly initialize the cluster number, Initialize initial random cluster centre values (initial random particle position),the degree of fuzziness m>1, and velocity of each particle and calculate the initial membership value, Until the termination conditions for new center we calculate the new membership values and also fitness function of PSO. Then calculate the velocity of particles for find the new center .these centers are given to FCM for good initialization.

The rest of paper is organized as follows .The backgrounds are given in Section II, including the FCM algorithm and the PSO technique. Section III presents our new proposed PSO based technique to determine cluster centroids and the number of cluster before carrying out FCM for image segmentation. Experiments and analysis are provided in section IV.finally, conclusion is made in the last part.

II. BACKGROUND

A. The Fuzzy C-Means Algorithm

Fuzzy clustering Fuzzy C-Means (FCM) is a method of clustering which allows one piece of data to belong to two or more clusters with different membership degrees between o and 1.it was first introduced by Dunn [START_REF] Dunn | A fuzzy relative of the ISODATA process and its use in detecting compact, well-separated clusters[END_REF] and modified by Bezdek [START_REF] Bezdek | Patteren recognition with fuzzy objective function algorithms[END_REF] .it is an iteration based method on optimization of the weighted squared error function

𝐽 𝑚 = 𝑢 𝑗𝑖 𝑚 𝑥 𝑖 -𝑐 𝑗 2 𝐶 𝑗 =1 𝑁 𝑖=1 (1)
where N is the number of data items ,c is the number of cluster ,m is a fuzzy factor with m>=1,cj is the centroids of the jth cluster,xi is the ith data, uij is the membership degree of xi in the jth cluster. The detailed FCM algorithm is described as follows.

1) Algorithm 1 Fuzzy C-Means

1) Set values for iteration terminating threshold ", cluster number c and fuzzy factor m.

2) Randomly initialize cluster centroid matrix C (q) with ck(k = 1; 2; :::; c).

3) Calculate the membership matrix U (q) according to C (q) with the following equation:

(2) 4) Calculate C (q+1) according to U (q) with the following equation:

(3) 5) Update U (q+1) according to C (q+1) with Eq. (2). 6) If max {U( q+1) -U (q) } ≤ ᵋ, then stop, otherwise, set q = q + 1 and go to step 3.

B. The Particle Swarm Optimization Technique

The algorithm of particle swarm optimization is an evolutionary computational model and is introduced by Kennedy and Eberhart (1995) [START_REF] Kennedy | Particle Swarm Optimization[END_REF]. Particle Swarm Optimization belongs to the class of swarm intelligent techniques that are used for to solve the Optimization problem in real life itself [START_REF] Ait-Aoudia | Medical Image Segmentation Using Particle Swarm Optimization[END_REF].PSO simulates the behavior of bird flocking .means, a group of bird finding the food randomly in an area. There is only one piece of food in the area being searched .all the birds do not know where is food is, but they know how far the food is in each iteration. So the best way to find the food is to follow the bird which is nearest to the food. Frocking behavior is exhibited when group of birds are foraging [START_REF] Naffouti | An Additive Image Watermarking Method Based On Particle Swarm Optimization[END_REF]. Each particle in PSO is updated by two best values [START_REF] Naffouti | An Additive Image Watermarking Method Based On Particle Swarm Optimization[END_REF]: pbest -Each particle keeps track of its coordinates in the solution space which are associated with the best solution (fitness) that has achieved so far by that particle. This value is called personal best, pbest. gbest -It is tracked by the PSO is the best value obtained so far by any particle in the neighbourhood of that particle. This value is called Global Best, gbest.

C. Algorithm 2 Particle Swarm Optimization

1) For each particle Initialize particle 2) For each particle Calculate fitness value 3) If the fitness value is better than the best fitness value (pbest) in history set current value as the new pbest 4) Choose the particle with the best fitness value of all the particles as the gbest 5) For each particle Calculate particle velocity according ) (4) 6) Update particle position according [START_REF] Ahmed | Segmentation Of Brain MR Images For Tumor Extraction By Combining Kmeans Clustering And Perona-Malik Anistropic Diffusion Model[END_REF] Where, vid is the velocity of particle in the d-dimension search space and is limited into [Vmin, Vmax]. Vmin and Vmax are respectively, the minimum and maximum the moving distance in one-step, pid is the position of ith particle i, pidbest is the individual best position of particle I, pgidbest is the gidth global best position in all particles, xid is the current position of particle i, rand () is a random number function and its value are between 0 and 1, w is the inertia weight, c1 and c2 are constants [START_REF] Naffouti | An Additive Image Watermarking Method Based On Particle Swarm Optimization[END_REF]. The FCM algorithm has some limitations that it requires initialization of cluster centroids and the number of cluster. So the PSO technique is applied to the MRI medical images for the purpose of initialization of cluster centroids, which could overcome the defects of FCM algorithm. On the whole, for good segmentation we use the Particle Swarm Optimization technique to trigger FCM For good initialization. We can randomly initialize the cluster number, Initialize initial random cluster centre values (initial random particle position),the degree of fuzziness m>1, and velocity of each particle and calculate the initial membership value. until the termination conditions for new center we calculate the new membership values and also fitness function of PSO. After that update the pbest and gbest values and calculate the velocity of particle for find the new center .These centers are given to FCM for good initialization. The proposed algorithm is as follows.

A. Algorithm 3 PSO_FCM algorithm 1) Calculate the filtered image.

2) Initialize Cluster numbers, Initialize initial random cluster centre values (initial random particle position), the degree of fuzziness m>1, and velocity of each particle. Here the segmentation can be done as first cluster, second cluster an third cluster. In this we are taking the cluster value three so here only three clusters have shown. As seen in table the initial center was taken by FCM randomly so after 70 iteration we got the results but using PSO_FCM we first take initial center randomly but after PSO finding the global best value and find the initial centers, that initial center we gives to FCM .The PSO_FCM results are shown in fig. 3 .In table 2 we seen the initial center it given by PSO to trigger FCM and also calculate the cluster center value by PSO .So after 40 iteration we got the results. So the computation time is very less than FCM. Sometimes FCM can be stuck between local minima but in PSO_FCM it gives better segmentation results.

Fig. 1 :

 1 Fig. 1: PSO results for finding global best value among the search space III. SUGGESTED APPROACH The Suggested algorithm is an approach which combines the Particle Swarm Optimization (PSO) techniques and Fuzzy C-Means (FCM) algorithm to perform image segmentation on Magnetic Resonance Imaging (MRI).The MRI images dataset are taken from the different MRI centre.The FCM algorithm has some limitations that it requires initialization of cluster centroids and the number of cluster. So the PSO technique is applied to the MRI medical images for the purpose of initialization of cluster centroids, which could overcome the defects of FCM algorithm. On the whole, for good segmentation we use the Particle Swarm Optimization technique to trigger FCM For good initialization. We can randomly initialize the cluster number, Initialize initial random cluster centre values (initial random particle position),the degree of fuzziness m>1, and velocity of each particle and calculate the initial membership value. until the termination conditions for new center we calculate the new membership values and also fitness function of PSO. After that update the pbest and gbest values and calculate the velocity of particle for find the new center .These centers are given to FCM for good initialization. The proposed algorithm is as follows.

3 )

 3 Calculate the initial membership value U 4) Repeat until Termination Condition 5) For each centre -Calculate next membership value U(k+1) -Calculate the fitness function or Objective Function -Update the pbst and gbest values -Calculate the velocity and position of particle (new centre calculation) -End for (step 5) 6) If not termination condition Go to 5 -End for (step 4) IV. RESULT AND DISCUSSION As can be seen from fig.2 the results of FCM are shown. The segmentation results of MRI images are seen.

Fig. 2 .

 2 Fig.2. Segmentation results of FCM (a) original image, (b) first cluster, (c) second cluster, (d) third cluster

Fig. 3 .

 3 Fig.3. Segmentation results of PSO_FCM (a )original image, (b) first cluster, (c) second cluster, (d) third cluster

Fig. 4 .Table 3 .Fig. 5 .

 435 Fig.4. Segmentation results of FCM (a )original image, (b) first cluster, (c) second cluster, (d) third cluster

Table 1 .

 1 Results of FCMThe Experimental results of MR images using PSO_FCM results are shown as below. PSO_FCM gives better segmentation results over FCM algorithm, also less computation complexity.

		.0445
	0.2138	0.9975
	0.2144	0.6936
	0.2135	0.3726
	0.2131	0.1221
	0.2138	0.5079

Table 2 .

 2 Results of PSO_ FCMSimulations are carried out for different Magnetic Resonance imaging (MRI) images.

	Initial center PSO	Final center PSO	Total iterations
	0.0213	0.0471
	0.1384	0.4123
	0.1401	0.3362
	0.1303	0.2715	40
	0.1382	0.5446
	0.1389	0.7364
	0.1389	0.9978

Table 4 .

 4 Results of PSO_ FCM V. CONCLUSIONS In this paper, we have combined the Particle Swarm Optimization (PSO) and Fuzzy C-Means (FCM) algorithm to perform image segmentation for MRI images. Our Suggested algorithm called PSO_FCM could decide the number of cluster and cluster centroids and pass these two values to carry out FCM algorithm. Showing the usefulness of global best values .It has made improvement on FCM for no need of random initialization. Extensive experimental results are shown and comparison with FCM and PSO_FCM.