Fuzzy system for image segmentation slow

[Unknown]

Hello,

I am currently developing an image segmentation application using the Codebook algorithm and with a fuzzy-system. The original algorithm first performs a learning on a certain number of frames in which it models the background over time and for each pixel. Basically each pixel information is split into 2 information : color & brightness distortions. When a new frame arrives, each pixel information is split the same way as during learning, and a matching between an observed pixel is searched in the background model based on color and brightness distortions (which have to be close enough according to thresholds).

I want to fuzzify this algorithm using FL.
I think it is better to avoid having 1 FL engine per pixel. So, I created one FL engine with 2 input variables (ColorDistortion and BrightnessDistortion) and 1 output variable (Decision) outside of the image parsing. However, for each pixel, I have to set new Terms for the BrightnessDistortion variable, as its thresholds differ between every pixel and depend on the background model.

Thus, the setting of rules has to be done for each pixel, since it needs all the variable terms to be set before.
My problem lies in the performances results. The processing of a single 640×480 frame takes up to 3 minutes at least.
Do you have an idea how I can improve the speed of the process ?

I will post the code a bit later if needed (I am currently using another computer).
Thanks a lot !

[Juan Rada-Vilela (admin)]

Hi Straton,

thank you for your post.

Indeed, it would be great if you could post your code for review. It seems to me that your solution was to create many rules within your engine, which would certainly deteriorate the performance. Once you post your code, I will try to give you some advice to increase the performance. Please, post your code using the FuzzyLite Language and C++ (fuzzylite) or Java (jfuzzylite).

Also, I hope you are using fuzzylite 5.0, especially because there are important performance improvements.

Cheers.

[Unknown]

Thank you for your answer. I effectively use FL 5.0, compiled with C++11.

I will try to make the code as clear as possible.
Everything lies in a CBFuzzyModel class, that declares some members :

fl::Engine* fuzzyEngineRGB;
fl::InputVariable* deltaColorVar;
fl::InputVariable* deltaIntensityVar;

At the creation of the instance of this class, the private method initCodebook() is called. Basically, it initialises the background model (the 2 vectors) and the fuzzy engine.

void CBFuzzyModel::initCodebook(int rows, int cols) {
	cbMain = new std::vector<codeword>*[rows];
	for(int i = 0; i < rows; ++i)
		cbMain[i] = new std::vector<codeword>[cols];

	cbCache = new std::vector<codeword>*[rows];
	for(int i = 0; i < rows; ++i)
		cbCache[i] = new std::vector<codeword>[cols];

	fuzzyEngineRGB = new fl::Engine("fuzzyEngineRGB");

	deltaColorVar = new fl::InputVariable;
	deltaColorVar->setName("DeltaColor");
	deltaColorVar->setRange(0.000, 255.000);
	deltaColorVar->addTerm(new fl::Trapezoid("COLOR_FAVORABLE", 0.000, 0.000, 10.0, 50.0));
	deltaColorVar->addTerm(new fl::Trapezoid("COLOR_DEFAVORABLE", 10.0, 50.0, 255.000, 255.000));
	fuzzyEngineRGB->addInputVariable(deltaColorVar);

	deltaIntensityVar = new fl::InputVariable;
	deltaIntensityVar->setName("DeltaIntensity");
	deltaIntensityVar->setRange(0.000, 442.000);
	fuzzyEngineRGB->addInputVariable(deltaIntensityVar);

	fl::OutputVariable* decision = new fl::OutputVariable;
	decision->setName("DecisionIsBackground");
	decision->setRange(0.000, 1.000);
	decision->setDefaultValue(fl::nan);
	decision->addTerm(new fl::Triangle("LOW", 0.0f, 1.0f/6.0f, 1.0f/3.0f));
	decision->addTerm(new fl::Triangle("MEDIUM", 1.0f/3.0f, 1.0f/2.0f, 2.0f/3.0f));
	decision->addTerm(new fl::Triangle("HIGH", 2.0f/3.0f, 5.0f/6.0f, 1.0f));
	fuzzyEngineRGB->addOutputVariable(decision);

	fuzzyEngineRGB->configure("AlgebraicProduct", "AlgebraicSum", "AlgebraicProduct", "AlgebraicSum", "Centroid");
}

Then, the model is updated using a new frame using the update() method. It takes in parameter the frame.
An explanation of the background model : it is represented by a vector of “codebooks”, one per pixel. One codebook is a vector of “Codewords” that represent one entry for the pixel from the learning (here it is a struct containing several values Bmin, Bmax, f, l…).
For the first learning frame, every pixel’s codebook is empty so 1 codeword is created in each codebook.
Starting from the 2nd learning frame, we test the existence of a matching in the pixel’s codebook using the fuzzy system in method fuzzyRGBTest(). It takes as parameters the color of the observation (xt) and the codeword we attempt to match.
Step III in the end of this method does some cleaning stuff.

void CBFuzzyModel::update(const Mat& frameColor) {
	if(t>  nbLearningFrames) return;
	for(int i=0;i<frameColor.rows;i++)
	{
		for(int j=0;j<frameColor.cols;j++)
		{
			//std::cout << "(" << j << ", " << i << ")" << std::endl;
			Vec3b pix =  frameColor.at<Vec3b>(i,j);
			std::vector<codeword>& cm =cbMain[i][j];
			float B = std::sqrt(pix[0]*pix[0]+ pix[1]*pix[1] + pix[2]*pix[2]);
			bool found = false;

			// Test each codeword
			for(unsigned int k=0;k<cm.size();k++)
			{
				// if (DEBUG) std::cout << "(" << i << ", " << j << ")" << std::endl;
		
				float xt[3] = {float(pix[2]), float(pix[1]), float(pix[0])};	// this is the color vector of the observed pixel

				if (fuzzyRGBTest(xt, cm[k]) && !found) // Matching found
				{
					found=true;
 					cm[k].R = (cm[k].f * cm[k].R + pix[2]) / (cm[k].f + 1);
					cm[k].G = (cm[k].f * cm[k].G + pix[1]) / (cm[k].f + 1);
					cm[k].B = (cm[k].f * cm[k].B + pix[0]) / (cm[k].f + 1);
					cm[k].Bmin = MIN(B, cm[k].Bmin);
					cm[k].Bmax = MAX(B, cm[k].Bmax);
					cm[k].l= MAX(cm[k].l, this->t - cm[k].last);
					cm[k].last=t;
					cm[k].f++;
				 }else{
					cm[k].l++;
				 }
			}
			if(!found) // no matching = create new codeword
			{
                                codeword n={};
				n.R = pix[2];
				n.G = pix[1];
				n.B = pix[0];
				n.Bmin=B;
				n.Bmax=B;
				n.f=1;
 				n.l=t-1;
				n.first=t;
				n.last=t;
				cm.push_back(n);
			}
		}
	}

	// step III wrap around lambda
	if (t == nbLearningFrames)
	{
		for(int i=0;i<frameColor.rows;i++)
		{
			for(int j=0;j<frameColor.cols;j++)
			{
				std::vector<codeword>& cm =cbMain[i][j];
				for(unsigned int k=0;k<cm.size();k++)
				{
					cm[k].l = MAX(cm[k].l, (nbLearningFrames - cm[k].last + cm[k].first - 1));
				}
				// on supprime les CW du main dont la MNRL est >= Tdel
				cm.erase( remove_if(cm.begin(), cm.end(), [&](codeword& c) { return c.l>Tdel;} ), cm.end() );
			}
		}
		std::cout << "Learning finished." << std::endl;
	}

	t++;
}

The fuzzyRGBTest() method does the following : compute the observed pixel’s brightness B and the color distorsion between observed pixel and the codeword cw.
Then, fuzzy thresholds for deltaIntensityVar terms are computed (in this code, Brightness and Intensity have the same meaning). Once computed, the deltaIntensityVar is emptied of previous terms, then filled with new corresponding Terms. Finally, the Ruleblock is defined and set in the engine. Finally the engine is processed after verifications, and this functions returns true if the defuzzified decision output value is > 0.5.

bool CBFuzzyModel::fuzzyRGBTest(const float pix[3], const codeword& cw) {
	float retValue = -1;
	float B = std::sqrt(pix[0]*pix[0] + pix[1]*pix[1] + pix[2]*pix[2]);
	float xt[3] = {float(pix[0]), float(pix[1]), float(pix[2])};
	float vm[3] = {cw.R, cw.G, cw.B};
	float colorDist = this->colorDist(xt, vm);

        // Compute fuzzy thresholds
	float gapBrightness = 15.0f;
	float divider = 4.0f;
	float brightnessMin = cw.Bmin-gapBrightness;
	float brightnessMax = cw.Bmax+gapBrightness;
	float intervalBrightness = brightnessMax - brightnessMin;
	for (int i=0 ; i<deltaIntensityVar->numberOfTerms() ; ++i)
		deltaIntensityVar->removeTerm(i);

	deltaIntensityVar->addTerm(new fl::Trapezoid("BRIGHTNESS_DEFAVORABLE1",
			0.000, 0.000, CLAMP(brightnessMin-intervalBrightness, 0.0f, 442.0f), brightnessMin) );
	deltaIntensityVar->addTerm(new fl::Triangle("BRIGHTNESS_MOY_FAVORABLE1",
			CLAMP(brightnessMin-intervalBrightness, 0.0f, 442.0f), brightnessMin, CLAMP(brightnessMin + intervalBrightness/divider, 0.0f, 442.0f) ));
	deltaIntensityVar->addTerm(new fl::Trapezoid("BRIGHTNESS_FAVORABLE",
			brightnessMin, CLAMP(brightnessMin + intervalBrightness/divider, 0.0f, 442.0f), CLAMP(brightnessMax - intervalBrightness/divider, 0.0f, 442.0f),
			brightnessMax));
	deltaIntensityVar->addTerm(new fl::Triangle("BRIGHTNESS_MOY_FAVORABLE2",
			CLAMP(brightnessMax - intervalBrightness/divider, 0.0f, 442.0f), brightnessMax, CLAMP(brightnessMax+intervalBrightness, 0.0f, 442.0f)));
	deltaIntensityVar->addTerm(new fl::Trapezoid("BRIGHTNESS_DEFAVORABLE2",
			brightnessMax,  CLAMP(brightnessMax+intervalBrightness, 0.0f, 442.0f), 442.0f, 442.0f));

	// RuleBlock RGB
	fl::RuleBlock* ruleblockRGB = new fl::RuleBlock;
	ruleblockRGB->setConjunction(new fl::Minimum);
	ruleblockRGB->setDisjunction(new fl::Maximum);
	ruleblockRGB->setActivation(new fl::Minimum);
	ruleblockRGB->addRule(fl::Rule::parse("if DeltaColor is COLOR_FAVORABLE and "	// +(+o) = +
			 "DeltaIntensity is not BRIGHTNESS_DEFAVORABLE1 and DeltaIntensity is not BRIGHTNESS_DEFAVORABLE2 "
					 "then DecisionIsBackground is HIGH", fuzzyEngineRGB));
	ruleblockRGB->addRule(fl::Rule::parse("if DeltaColor is COLOR_DEFAVORABLE and "	// -+ = o
					 "DeltaIntensity is BRIGHTNESS_FAVORABLE "
					 "then DecisionIsBackground is MEDIUM", fuzzyEngineRGB));
	ruleblockRGB->addRule(fl::Rule::parse("if DeltaColor is COLOR_FAVORABLE and "	// +- = o
			 "DeltaIntensity is BRIGHTNESS_DEFAVORABLE1 or DeltaIntensity is BRIGHTNESS_DEFAVORABLE2 "
					 "then DecisionIsBackground is LOW", fuzzyEngineRGB));
	ruleblockRGB->addRule(fl::Rule::parse("if DeltaColor is COLOR_DEFAVORABLE and "	// -(o-) = -
					 "DeltaIntensity is not BRIGHTNESS_FAVORABLE "
					"then DecisionIsBackground is LOW", fuzzyEngineRGB));
	fuzzyEngineRGB->addRuleBlock(ruleblockRGB);

	std::string status;
	if (not fuzzyEngineRGB->isReady(&status)) {
		printf("Engine not ready.\n");
		throw fl::Exception("Engine not ready. "
			"The following errors were encountered:\n" + status, FL_AT);
		return -1;
	}
	else {
		deltaIntensityVar->setInputValue(abs(B));
		fl::InputVariable* deltaColorVar = fuzzyEngineRGB->getInputVariable("DeltaColor");
		deltaColorVar->setInputValue(colorDist);

		fuzzyEngineRGB->process();

		fl::OutputVariable* decision = fuzzyEngineRGB->getOutputVariable("DecisionIsBackground");
		retValue = decision->getOutputValue();
	}
	return retValue > fuzzyResultThresh;
}

[Juan Rada-Vilela (admin)]

Hi,

you have a number of problems in your code.

(1) The Centroid defuzzifier is computationally expensive. You may want to decrease its resolution by passing another parameter to the configure(..., "Centroid", 100) method, where 100 is the number integration points. The smaller the resolution, the faster the algorithm is, but its accuracy decreases. The larger the resolution, the slower the algorithm is, but its accuracy increases. By default, the resolution is set to 200 (revise IntegralDefuzzifier.[h|cpp]).

(2) You are executing the method fuzzyRGBTest $i\times j\times k$, and there are several problems in this method.
(2.1) deltaIntensityVar->removeTerm(i); will remove the term from the vector, but will not delete it, therefore you are leaking memory, not to mention that you need to remove terms using for i=n-1 to 0 and not for i = 0 to n. You could do delete deltaIntensityVar->removeTerm(i);, but you will likely cause a segmentation fault because you are not deleting the rule blocks correctly, and these will have pointers to the terms you delete.
(2.2) fuzzyEngineRGB->addRuleBlock(ruleblockRGB); you continue to add rule blocks and rules to the engine, yet I cannot see where you remove *and delete* other rule blocks.
(2.3) By not removing rule blocks, the engine needs to process every rule block added upon process(), which seems to me is what is causing the slow response.

You need to rethink your implementation. You should consider designing multiple fuzzy engines outside the $i,j,k$ for-loop and choose the right engine within the for-loop without changing its configuration. Even better would be to design a single fuzzy engine that takes into account the variable intervalBrightness, and create rules that modify your current rules only once, but I am not sure if this is possible given that I am not familiar with what you are trying to achieve.

Hope this helps somehow.

Cheers.

[Unknown]

Thanks a lot for your advices Juan!
These changes effectively improved the response speed by at least 2 (when one frame was previously processed in 3 minutes, it now only takes 1 or a little less).

Changes :
– (1) added resolution parameter 100 in the configure() method
– (2.1) modified in fuzzyRGBTest() :

for (int i=0 ; i<deltaIntensityVar->numberOfTerms() ; ++i)
		deltaIntensityVar->removeTerm(i);

to

for (int i=numberOfTerms()-1 ; i>0 ; --i)
	delete deltaIntensityVar->removeTerm(i);

– (2.2 – 2.3) added in fuzzyRGBTest() :

if (fuzzyEngineRGB->hasRuleBlock("RuleblockRGB"))
	delete fuzzyEngineRGB->removeRuleblock("RuleblockRGB");

Considering your suggestion of having multiple engines and avoid as much as possible their modification inside the for-loops, this would mean having I*J*K different engines, that is, K engines per pixel, one per codeword (K is not equal for all the pixels).

Though this would not really be a problem in terms of development (I could either set up a pointer to an Engine into the codeword struct or manage a vector of I vectors of J vectors of K Engines), but do you think it would cause a memory problem? Is the overall Engine structure heavy in memory?
Anyway, I think this would be profitable this way.

design a single fuzzy engine that takes into account the variable intervalBrightness, and create rules that modify your current rules only once,

I am not certain to understand what you mean. The Brightness variable depends on brightnessMin and brightnessMax values, which are codeword values. Thus, rules have to change for each codeword in to take new thresholds into account in the new rules.

[Juan Rada-Vilela (admin)]

Hi,

I think you should modify existing terms instead of recreating them, thereby not requiring to add new rule blocks every time. In fuzzyRGBTest, go over all the terms, modify their parameters, and keep going. In addition, you add the rule block in initCodebook and not in fuzzyRGBTest. This should significantly increase performance.

Furthermore, you could create multiple engines, divide your frame into regions, and assign each region an engine. Each engine would run in a separate thread, thereby utilising multiple cores in parallel, which would vastly increase the performance.

Cheers.

[Unknown]

I think you should modify existing terms instead of recreating them, thereby not requiring to add new rule blocks every time. In fuzzyRGBTest, go over all the terms, modify their parameters, and keep going. In addition, you add the rule block in initCodebook and not in fuzzyRGBTest. This should significantly increase performance.

Very true.
Since fuzzy terms are pointers, modifying their inner values directly affect the terms set in the variable once in initCodebook(). I don’t know why I didn’t do it in the first time.

Furthermore, you could create multiple engines, divide your frame into regions, and assign each region an engine. Each engine would run in a separate thread, thereby utilising multiple cores in parallel, which would vastly increase the performance.

Definitely. If the process speed doesn’t get sufficient enough after previous enhancements, I shall multithread the code. This development is not for production, but research. Btw, I didn’t see any bibtex entry for your work. Could you provide one if you want your work to be referenced ? Oops. That was on the home page. Sorry, my bad.

Thank a LOT.

[Author]

Posts