|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//#include "traster.h"
|
|
Toshihiro Shimizu |
890ddd |
#include "tcolorutils.h"
|
|
Toshihiro Shimizu |
890ddd |
#include "tmathutil.h"
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#include <set></set>
|
|
Toshihiro Shimizu |
890ddd |
#include <list></list>
|
|
Campbell Barton |
3b0737 |
#include <cmath></cmath>
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
typedef float KEYER_FLOAT;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
|
e280ae |
#ifdef _MSC_VER
|
|
Toshihiro Shimizu |
890ddd |
#define ISNAN _isnan
|
|
Toshihiro Shimizu |
890ddd |
#else
|
|
Michał Janiszewski |
b86749 |
#define ISNAN std::isnan
|
|
Toshihiro Shimizu |
890ddd |
#endif
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//#define CLUSTER_ELEM_CONTAINER_IS_A_SET
|
|
Toshihiro Shimizu |
890ddd |
//#define WITH_ALPHA_IN_STATISTICS
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
class ClusterStatistic {
|
|
Toshihiro Shimizu |
890ddd |
public:
|
|
Campbell Barton |
a6cacc |
KEYER_FLOAT sumComponents[3]; // vector 3x1
|
|
Shinya Kitaoka |
120a6e |
unsigned int elemsCount;
|
|
Campbell Barton |
a6cacc |
KEYER_FLOAT matrixR[9]; // matrix 3x3 = sum(x * transposed(x))
|
|
Campbell Barton |
a6cacc |
// where x are the pixels in the cluster
|
|
Toshihiro Shimizu |
890ddd |
|
|
Campbell Barton |
a6cacc |
KEYER_FLOAT covariance[9]; // covariance matrix
|
|
Shinya Kitaoka |
120a6e |
TPoint sumCoords;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#ifdef WITH_ALPHA_IN_STATISTICS
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT sumAlpha;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#endif
|
|
Toshihiro Shimizu |
890ddd |
};
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
class ClusterElem {
|
|
Toshihiro Shimizu |
890ddd |
public:
|
|
Shinya Kitaoka |
120a6e |
ClusterElem(unsigned char _r, unsigned char _g, unsigned char _b,
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT _a, unsigned int _x = 0, unsigned int _y = 0)
|
|
Shinya Kitaoka |
120a6e |
: r(toDouble(_r))
|
|
Shinya Kitaoka |
120a6e |
, g(toDouble(_g))
|
|
Shinya Kitaoka |
120a6e |
, b(toDouble(_b))
|
|
Shinya Kitaoka |
120a6e |
, a(_a)
|
|
Shinya Kitaoka |
120a6e |
, x(_x)
|
|
Shinya Kitaoka |
120a6e |
, y(_y)
|
|
Shinya Kitaoka |
120a6e |
, pix32(TPixel32(_r, _g, _b)) {}
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
~ClusterElem() {}
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
static KEYER_FLOAT toDouble(unsigned char chan) {
|
|
Shinya Kitaoka |
120a6e |
return ((KEYER_FLOAT)chan) * (KEYER_FLOAT)(1.0 / 255.0);
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
unsigned int x;
|
|
Shinya Kitaoka |
120a6e |
unsigned int y;
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT r;
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT g;
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT b;
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT a;
|
|
Shinya Kitaoka |
120a6e |
TPixel32 pix32;
|
|
Toshihiro Shimizu |
890ddd |
};
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#ifdef CLUSTER_ELEM_CONTAINER_IS_A_SET
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
typedef std::set<clusterelem *=""> ClusterElemContainer;</clusterelem>
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#else
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
typedef std::vector<clusterelem *=""> ClusterElemContainer;</clusterelem>
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#endif
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
class Cluster {
|
|
Toshihiro Shimizu |
890ddd |
public:
|
|
Shinya Kitaoka |
120a6e |
Cluster();
|
|
Shinya Kitaoka |
120a6e |
Cluster(const Cluster &rhs);
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
~Cluster();
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
void computeCovariance();
|
|
Shinya Kitaoka |
120a6e |
void insert(ClusterElem *elem);
|
|
Shinya Kitaoka |
120a6e |
void computeStatistics();
|
|
Shinya Kitaoka |
120a6e |
void getMeanAxis(KEYER_FLOAT axis[3]);
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
ClusterStatistic statistic;
|
|
Shinya Kitaoka |
120a6e |
ClusterElemContainer data;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT eigenVector[3];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT eigenValue;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
private:
|
|
Shinya Kitaoka |
120a6e |
void operator=(const Cluster &);
|
|
Toshihiro Shimizu |
890ddd |
};
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
typedef std::vector<cluster *=""> ClusterContainer;</cluster>
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//----------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
void chooseLeafToClusterize(ClusterContainer::iterator &itRet,
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT &eigenValue, KEYER_FLOAT eigenVector[3],
|
|
Shinya Kitaoka |
120a6e |
ClusterContainer &clusters);
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
void split(Cluster *subcluster1, Cluster *subcluster2,
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT eigenVector[3], Cluster *cluster);
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
void SolveCubic(KEYER_FLOAT a, /* coefficient of x^3 */
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT b, /* coefficient of x^2 */
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT c, /* coefficient of x */
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT d, /* constant term */
|
|
Shinya Kitaoka |
120a6e |
int *solutions, /* # of distinct solutions */
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT *x); /* array of solutions */
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
unsigned short int calcCovarianceEigenValues(const KEYER_FLOAT covariance[9],
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT eigenValues[3]);
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//----------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
void split(Cluster *subcluster1, Cluster *subcluster2,
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT eigenVector[3], Cluster *cluster) {
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT n = (KEYER_FLOAT)cluster->statistic.elemsCount;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT mean[3];
|
|
Shinya Kitaoka |
120a6e |
mean[0] = cluster->statistic.sumComponents[0] / n;
|
|
Shinya Kitaoka |
120a6e |
mean[1] = cluster->statistic.sumComponents[1] / n;
|
|
Shinya Kitaoka |
120a6e |
mean[2] = cluster->statistic.sumComponents[2] / n;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
ClusterElemContainer::const_iterator it = cluster->data.begin();
|
|
Shinya Kitaoka |
120a6e |
for (; it != cluster->data.end(); ++it) {
|
|
Shinya Kitaoka |
120a6e |
ClusterElem *elem = *it;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT r = (KEYER_FLOAT)elem->r;
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT g = (KEYER_FLOAT)elem->g;
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT b = (KEYER_FLOAT)elem->b;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
// cluster->data.erase(it);
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
if (eigenVector[0] * r + eigenVector[1] * g + eigenVector[2] * b <=
|
|
Shinya Kitaoka |
120a6e |
eigenVector[0] * mean[0] + eigenVector[1] * mean[1] +
|
|
Shinya Kitaoka |
120a6e |
eigenVector[2] * mean[2])
|
|
Shinya Kitaoka |
120a6e |
subcluster1->insert(elem);
|
|
Shinya Kitaoka |
120a6e |
else
|
|
Shinya Kitaoka |
120a6e |
subcluster2->insert(elem);
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//----------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
void chooseLeafToClusterize(ClusterContainer::iterator &itRet,
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT &eigenValue, KEYER_FLOAT eigenVector[3],
|
|
Shinya Kitaoka |
120a6e |
ClusterContainer &clusters) {
|
|
Shinya Kitaoka |
120a6e |
itRet = clusters.end();
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
ClusterContainer::iterator itFound = clusters.end();
|
|
Shinya Kitaoka |
120a6e |
bool found = false;
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT maxEigenValue = 0.0;
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
unsigned short int multeplicity = 0;
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
ClusterContainer::iterator it = clusters.begin();
|
|
Shinya Kitaoka |
120a6e |
for (; it != clusters.end(); ++it) {
|
|
Shinya Kitaoka |
120a6e |
unsigned short int tmpMulteplicity = 0;
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT tmpEigenValue;
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
Cluster *cluster = *it;
|
|
Campbell Barton |
a6cacc |
// Calculates the covariance matrix.
|
|
Shinya Kitaoka |
120a6e |
const KEYER_FLOAT *clusterCovariance = cluster->statistic.covariance;
|
|
Shinya Kitaoka |
120a6e |
assert(!ISNAN(clusterCovariance[0]));
|
|
Shinya Kitaoka |
120a6e |
|
|
shun-iwasawa |
7cd1ff |
// Calculate the eigenvalues of the covariance matrix of the cluster
|
|
shun-iwasawa |
7cd1ff |
// statistics
|
|
Campbell Barton |
a6cacc |
// (because the array is symmetrical the eigenvalues are all real)
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT eigenValues[3];
|
|
Shinya Kitaoka |
120a6e |
tmpMulteplicity = calcCovarianceEigenValues(clusterCovariance, eigenValues);
|
|
Shinya Kitaoka |
120a6e |
assert(tmpMulteplicity > 0);
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
tmpEigenValue = std::max({eigenValues[0], eigenValues[1], eigenValues[2]});
|
|
Shinya Kitaoka |
120a6e |
cluster->eigenValue = tmpEigenValue;
|
|
Shinya Kitaoka |
120a6e |
|
|
Campbell Barton |
a6cacc |
// Check if there are any cluster updates to search for.
|
|
Shinya Kitaoka |
120a6e |
if (itFound == clusters.end()) {
|
|
Shinya Kitaoka |
120a6e |
itFound = it;
|
|
Shinya Kitaoka |
120a6e |
maxEigenValue = tmpEigenValue;
|
|
Shinya Kitaoka |
120a6e |
multeplicity = tmpMulteplicity;
|
|
Shinya Kitaoka |
120a6e |
found = true;
|
|
Shinya Kitaoka |
120a6e |
} else {
|
|
Shinya Kitaoka |
120a6e |
if (tmpEigenValue > maxEigenValue) {
|
|
Shinya Kitaoka |
120a6e |
itFound = it;
|
|
Shinya Kitaoka |
120a6e |
maxEigenValue = tmpEigenValue;
|
|
Shinya Kitaoka |
120a6e |
multeplicity = tmpMulteplicity;
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
if (found) {
|
|
Shinya Kitaoka |
120a6e |
assert(multeplicity > 0);
|
|
Shinya Kitaoka |
120a6e |
itRet = itFound;
|
|
Shinya Kitaoka |
120a6e |
eigenValue = maxEigenValue;
|
|
Shinya Kitaoka |
120a6e |
|
|
Campbell Barton |
a6cacc |
// Calculates the eigenvector related to 'maxEigenValue'
|
|
Shinya Kitaoka |
120a6e |
Cluster *clusterFound = *itFound;
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
assert(multeplicity > 0);
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT tmpMatrixM[9];
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
const KEYER_FLOAT *clusterCovariance = clusterFound->statistic.covariance;
|
|
Shinya Kitaoka |
120a6e |
int i = 0;
|
|
Shinya Kitaoka |
120a6e |
for (; i < 9; ++i) tmpMatrixM[i] = clusterCovariance[i];
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
tmpMatrixM[0] -= maxEigenValue;
|
|
Shinya Kitaoka |
120a6e |
tmpMatrixM[4] -= maxEigenValue;
|
|
Shinya Kitaoka |
120a6e |
tmpMatrixM[8] -= maxEigenValue;
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
for (i = 0; i < 3; ++i) eigenVector[i] = 0.0;
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
if (multeplicity == 1) {
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT u11 =
|
|
Shinya Kitaoka |
120a6e |
tmpMatrixM[4] * tmpMatrixM[8] - tmpMatrixM[5] * tmpMatrixM[5];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT u12 =
|
|
Shinya Kitaoka |
120a6e |
tmpMatrixM[2] * tmpMatrixM[5] - tmpMatrixM[1] * tmpMatrixM[8];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT u13 =
|
|
Shinya Kitaoka |
120a6e |
tmpMatrixM[1] * tmpMatrixM[5] - tmpMatrixM[2] * tmpMatrixM[5];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT u22 =
|
|
Shinya Kitaoka |
120a6e |
tmpMatrixM[0] * tmpMatrixM[8] - tmpMatrixM[2] * tmpMatrixM[2];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT u23 =
|
|
Shinya Kitaoka |
120a6e |
tmpMatrixM[1] * tmpMatrixM[2] - tmpMatrixM[5] * tmpMatrixM[0];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT u33 =
|
|
Shinya Kitaoka |
120a6e |
tmpMatrixM[0] * tmpMatrixM[4] - tmpMatrixM[1] * tmpMatrixM[1];
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT uMax = std::max({u11, u12, u13, u22, u23, u33});
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
if (uMax == u11) {
|
|
Shinya Kitaoka |
120a6e |
eigenVector[0] = u11;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[1] = u12;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[2] = u13;
|
|
Shinya Kitaoka |
120a6e |
} else if (uMax == u12) {
|
|
Shinya Kitaoka |
120a6e |
eigenVector[0] = u12;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[1] = u22;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[2] = u23;
|
|
Shinya Kitaoka |
120a6e |
} else if (uMax == u13) {
|
|
Shinya Kitaoka |
120a6e |
eigenVector[0] = u13;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[1] = u23;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[2] = u33;
|
|
Shinya Kitaoka |
120a6e |
} else if (uMax == u22) {
|
|
Shinya Kitaoka |
120a6e |
eigenVector[0] = u12;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[1] = u22;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[2] = u23;
|
|
Shinya Kitaoka |
120a6e |
} else if (uMax == u23) {
|
|
Shinya Kitaoka |
120a6e |
eigenVector[0] = u13;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[1] = u23;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[2] = u33;
|
|
Shinya Kitaoka |
120a6e |
} else if (uMax == u33) {
|
|
Shinya Kitaoka |
120a6e |
eigenVector[0] = u13;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[1] = u23;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[2] = u33;
|
|
Shinya Kitaoka |
120a6e |
} else {
|
|
Shinya Kitaoka |
120a6e |
assert(false && "impossibile!!");
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
} else if (multeplicity == 2) {
|
|
Shinya Kitaoka |
120a6e |
short int row = -1;
|
|
Shinya Kitaoka |
120a6e |
short int col = -1;
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT mMax =
|
|
Shinya Kitaoka |
120a6e |
std::max({tmpMatrixM[0], tmpMatrixM[1], tmpMatrixM[2], tmpMatrixM[4],
|
|
Shinya Kitaoka |
120a6e |
tmpMatrixM[5], tmpMatrixM[8]});
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
if (mMax == tmpMatrixM[0]) {
|
|
Shinya Kitaoka |
120a6e |
row = 1;
|
|
Shinya Kitaoka |
120a6e |
col = 1;
|
|
Shinya Kitaoka |
120a6e |
} else if (mMax == tmpMatrixM[1]) {
|
|
Shinya Kitaoka |
120a6e |
row = 1;
|
|
Shinya Kitaoka |
120a6e |
col = 2;
|
|
Shinya Kitaoka |
120a6e |
} else if (mMax == tmpMatrixM[2]) {
|
|
Shinya Kitaoka |
120a6e |
row = 1;
|
|
Shinya Kitaoka |
120a6e |
col = 3;
|
|
Shinya Kitaoka |
120a6e |
} else if (mMax == tmpMatrixM[4]) {
|
|
Shinya Kitaoka |
120a6e |
row = 2;
|
|
Shinya Kitaoka |
120a6e |
col = 2;
|
|
Shinya Kitaoka |
120a6e |
} else if (mMax == tmpMatrixM[5]) {
|
|
Shinya Kitaoka |
120a6e |
row = 2;
|
|
Shinya Kitaoka |
120a6e |
col = 3;
|
|
Shinya Kitaoka |
120a6e |
} else if (mMax == tmpMatrixM[8]) {
|
|
Shinya Kitaoka |
120a6e |
row = 3;
|
|
Shinya Kitaoka |
120a6e |
col = 3;
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
if (row == 1) {
|
|
Shinya Kitaoka |
120a6e |
if (col == 1 || col == 2) {
|
|
Shinya Kitaoka |
120a6e |
eigenVector[0] = -tmpMatrixM[1];
|
|
Shinya Kitaoka |
120a6e |
eigenVector[1] = tmpMatrixM[0];
|
|
Shinya Kitaoka |
120a6e |
eigenVector[2] = 0.0;
|
|
Shinya Kitaoka |
120a6e |
} else {
|
|
Shinya Kitaoka |
120a6e |
eigenVector[0] = tmpMatrixM[2];
|
|
Shinya Kitaoka |
120a6e |
eigenVector[1] = 0.0;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[2] = -tmpMatrixM[0];
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
} else if (row == 2) {
|
|
Shinya Kitaoka |
120a6e |
eigenVector[0] = 0.0;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[1] = -tmpMatrixM[5];
|
|
Shinya Kitaoka |
120a6e |
eigenVector[2] = tmpMatrixM[4];
|
|
Shinya Kitaoka |
120a6e |
} else if (row == 3) {
|
|
Shinya Kitaoka |
120a6e |
eigenVector[0] = 0.0;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[1] = -tmpMatrixM[8];
|
|
Shinya Kitaoka |
120a6e |
eigenVector[2] = tmpMatrixM[5];
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
} else if (multeplicity == 3) {
|
|
Shinya Kitaoka |
120a6e |
eigenVector[0] = 1.0;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[1] = 0.0;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[2] = 0.0;
|
|
Shinya Kitaoka |
120a6e |
} else {
|
|
Shinya Kitaoka |
120a6e |
assert(false && "impossibile!!");
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
|
|
Campbell Barton |
a6cacc |
// Normalization of calculated eigenvector.
|
|
Shinya Kitaoka |
120a6e |
/*
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT eigenVectorMagnitude = sqrt(eigenVector[0]*eigenVector[0] +
|
|
Shinya Kitaoka |
120a6e |
eigenVector[1]*eigenVector[1] +
|
|
Shinya Kitaoka |
120a6e |
eigenVector[2]*eigenVector[2]);
|
|
Shinya Kitaoka |
120a6e |
assert(eigenVectorMagnitude > 0);
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
eigenVector[0] /= eigenVectorMagnitude;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[1] /= eigenVectorMagnitude;
|
|
Shinya Kitaoka |
120a6e |
eigenVector[2] /= eigenVectorMagnitude;
|
|
Shinya Kitaoka |
120a6e |
*/
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
clusterFound->eigenVector[0] = eigenVector[0];
|
|
Shinya Kitaoka |
120a6e |
clusterFound->eigenVector[1] = eigenVector[1];
|
|
Shinya Kitaoka |
120a6e |
clusterFound->eigenVector[2] = eigenVector[2];
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
assert(!ISNAN(eigenVector[0]));
|
|
Shinya Kitaoka |
120a6e |
assert(!ISNAN(eigenVector[1]));
|
|
Shinya Kitaoka |
120a6e |
assert(!ISNAN(eigenVector[2]));
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//----------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
unsigned short int calcCovarianceEigenValues(
|
|
Shinya Kitaoka |
120a6e |
const KEYER_FLOAT clusterCovariance[9], KEYER_FLOAT eigenValues[3]) {
|
|
Shinya Kitaoka |
120a6e |
unsigned short int multeplicity = 0;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT a11 = clusterCovariance[0];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT a12 = clusterCovariance[1];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT a13 = clusterCovariance[2];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT a22 = clusterCovariance[4];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT a23 = clusterCovariance[5];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT a33 = clusterCovariance[8];
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT c0 =
|
|
Shinya Kitaoka |
120a6e |
(KEYER_FLOAT)(a11 * a22 * a33 + 2.0 * a12 * a13 * a23 - a11 * a23 * a23 -
|
|
Shinya Kitaoka |
120a6e |
a22 * a13 * a13 - a33 * a12 * a12);
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT c1 = (KEYER_FLOAT)(a11 * a22 - a12 * a12 + a11 * a33 - a13 * a13 +
|
|
Shinya Kitaoka |
120a6e |
a22 * a33 - a23 * a23);
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT c2 = (KEYER_FLOAT)(a11 + a22 + a33);
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
int solutionsCount = 0;
|
|
Shinya Kitaoka |
120a6e |
SolveCubic((KEYER_FLOAT)-1.0, c2, -c1, c0, &solutionsCount, eigenValues);
|
|
Shinya Kitaoka |
120a6e |
assert(solutionsCount > 0);
|
|
Shinya Kitaoka |
120a6e |
multeplicity = 4 - solutionsCount;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
assert(!ISNAN(eigenValues[0]));
|
|
Shinya Kitaoka |
120a6e |
assert(!ISNAN(eigenValues[1]));
|
|
Shinya Kitaoka |
120a6e |
assert(!ISNAN(eigenValues[2]));
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
assert(multeplicity > 0);
|
|
Shinya Kitaoka |
120a6e |
return multeplicity;
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//----------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
void SolveCubic(KEYER_FLOAT a, /* coefficient of x^3 */
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT b, /* coefficient of x^2 */
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT c, /* coefficient of x */
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT d, /* constant term */
|
|
Shinya Kitaoka |
120a6e |
int *solutions, /* # of distinct solutions */
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT *x) /* array of solutions */
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Shinya Kitaoka |
120a6e |
static const KEYER_FLOAT epsilon = (KEYER_FLOAT)0.0001;
|
|
Shinya Kitaoka |
120a6e |
if (a != 0 && fabs(b - 0.0) <= epsilon && fabs(c - 0.0) <= epsilon &&
|
|
Shinya Kitaoka |
120a6e |
fabs(d - 0.0) <= epsilon)
|
|
Shinya Kitaoka |
120a6e |
// if(a != 0 && b == 0 && c == 0 && d == 0)
|
|
Shinya Kitaoka |
120a6e |
{
|
|
Shinya Kitaoka |
120a6e |
*solutions = 1;
|
|
Shinya Kitaoka |
120a6e |
x[0] = x[1] = x[2] = 0.0;
|
|
Shinya Kitaoka |
120a6e |
return;
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT a1 = (KEYER_FLOAT)(b / a);
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT a2 = (KEYER_FLOAT)(c / a);
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT a3 = (KEYER_FLOAT)(d / a);
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT Q = (KEYER_FLOAT)((a1 * a1 - 3.0 * a2) / 9.0);
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT R =
|
|
Shinya Kitaoka |
120a6e |
(KEYER_FLOAT)((2.0 * a1 * a1 * a1 - 9.0 * a1 * a2 + 27.0 * a3) / 54.0);
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT R2_Q3 = (KEYER_FLOAT)(R * R - Q * Q * Q);
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT theta;
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT PI = (KEYER_FLOAT)3.1415926535897932384626433832795;
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
if (R2_Q3 <= 0) {
|
|
Shinya Kitaoka |
120a6e |
*solutions = 3;
|
|
Shinya Kitaoka |
120a6e |
theta = (KEYER_FLOAT)acos(R / sqrt(Q * Q * Q));
|
|
Shinya Kitaoka |
120a6e |
x[0] = (KEYER_FLOAT)(-2.0 * sqrt(Q) * cos(theta / 3.0) - a1 / 3.0);
|
|
Shinya Kitaoka |
120a6e |
x[1] = (KEYER_FLOAT)(-2.0 * sqrt(Q) * cos((theta + 2.0 * PI) / 3.0) -
|
|
Shinya Kitaoka |
120a6e |
a1 / 3.0);
|
|
Shinya Kitaoka |
120a6e |
x[2] = (KEYER_FLOAT)(-2.0 * sqrt(Q) * cos((theta + 4.0 * PI) / 3.0) -
|
|
Shinya Kitaoka |
120a6e |
a1 / 3.0);
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
assert(!ISNAN(x[0]));
|
|
Shinya Kitaoka |
120a6e |
assert(!ISNAN(x[1]));
|
|
Shinya Kitaoka |
120a6e |
assert(!ISNAN(x[2]));
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
/*
|
|
Shinya Kitaoka |
120a6e |
long KEYER_FLOAT v;
|
|
Shinya Kitaoka |
120a6e |
v = x[0];
|
|
Shinya Kitaoka |
120a6e |
assert(areAlmostEqual(a*v*v*v+b*v*v+c*v+d, 0.0));
|
|
Shinya Kitaoka |
120a6e |
v = x[1];
|
|
Shinya Kitaoka |
120a6e |
assert(areAlmostEqual(a*v*v*v+b*v*v+c*v+d, 0.0));
|
|
Shinya Kitaoka |
120a6e |
v = x[2];
|
|
Shinya Kitaoka |
120a6e |
assert(areAlmostEqual(a*v*v*v+b*v*v+c*v+d, 0.0));
|
|
Shinya Kitaoka |
120a6e |
*/
|
|
Shinya Kitaoka |
120a6e |
} else {
|
|
Shinya Kitaoka |
120a6e |
*solutions = 1;
|
|
Shinya Kitaoka |
120a6e |
x[0] = (KEYER_FLOAT)pow((float)(sqrt(R2_Q3) + fabs(R)), (float)(1 / 3.0));
|
|
Shinya Kitaoka |
120a6e |
x[0] += (KEYER_FLOAT)(Q / x[0]);
|
|
Shinya Kitaoka |
120a6e |
x[0] *= (KEYER_FLOAT)((R < 0.0) ? 1 : -1);
|
|
Shinya Kitaoka |
120a6e |
x[0] -= (KEYER_FLOAT)(a1 / 3.0);
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
assert(!ISNAN(x[0]));
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
/*
|
|
Shinya Kitaoka |
120a6e |
long KEYER_FLOAT v;
|
|
Shinya Kitaoka |
120a6e |
v = x[0];
|
|
Shinya Kitaoka |
120a6e |
assert(areAlmostEqual(a*v*v*v+b*v*v+c*v+d, 0.0));
|
|
Shinya Kitaoka |
120a6e |
*/
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//----------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Campbell Barton |
8c6c57 |
static void clusterize(ClusterContainer &clusters, int clustersCount) {
|
|
Shinya Kitaoka |
120a6e |
unsigned int clustersSize = clusters.size();
|
|
Shinya Kitaoka |
120a6e |
assert(clustersSize >= 1);
|
|
Shinya Kitaoka |
120a6e |
|
|
Campbell Barton |
a6cacc |
// Ensure the clusters are always leaves.
|
|
Campbell Barton |
a6cacc |
// Tree calculated using the algorithm described by Orchard TSE - Bouman.
|
|
Shinya Kitaoka |
120a6e |
// (c.f.r. "Color Quantization of Images" - M.Orchard, C. Bouman)
|
|
Shinya Kitaoka |
120a6e |
|
|
Campbell Barton |
a6cacc |
// number of iterations , the number of clusters = number of iterations + 1
|
|
Shinya Kitaoka |
120a6e |
int m = clustersCount - 1;
|
|
Shinya Kitaoka |
120a6e |
int i = 0;
|
|
Shinya Kitaoka |
120a6e |
for (; i < m; ++i) {
|
|
Campbell Barton |
a6cacc |
// Choose the cluster leaf of the tree (the cluster in
|
|
Campbell Barton |
a6cacc |
// ClusterContainer "clusters") that has the highest eigenvalue, ie
|
|
Campbell Barton |
a6cacc |
// The cluster that has higher variance axis
|
|
Campbell Barton |
a6cacc |
// (which is the eigenvector corresponding to the largest eigenvalue).
|
|
Campbell Barton |
a6cacc |
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT eigenValue = 0.0;
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT eigenVector[3] = {0.0, 0.0, 0.0};
|
|
Shinya Kitaoka |
120a6e |
ClusterContainer::iterator itChoosedCluster;
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
chooseLeafToClusterize(itChoosedCluster, eigenValue, eigenVector, clusters);
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
assert(itChoosedCluster != clusters.end());
|
|
Shinya Kitaoka |
120a6e |
Cluster *choosedCluster = *itChoosedCluster;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#if 0
|
|
Toshihiro Shimizu |
890ddd |
|
|
Campbell Barton |
a6cacc |
// If the cluster chosen for the subdivision contains single
|
|
Campbell Barton |
a6cacc |
// element means that there's nothing left to divide up and exit
|
|
Campbell Barton |
a6cacc |
// the loop.
|
|
Campbell Barton |
a6cacc |
// This happens when checking how many more clusters of elements
|
|
Campbell Barton |
a6cacc |
// there are in the initial cluste.
|
|
Toshihiro Shimizu |
890ddd |
if(choosedCluster->statistic.elemsCount == 1)
|
|
Toshihiro Shimizu |
890ddd |
break;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#else
|
|
Toshihiro Shimizu |
890ddd |
|
|
Campbell Barton |
a6cacc |
// A cluster that has only one element doesn't make much sense to exist,
|
|
Campbell Barton |
a6cacc |
// It also creates problems in the computation of the covariance matrix.
|
|
Campbell Barton |
a6cacc |
// Stop when the cluster contains less than 4 elements.
|
|
Shinya Kitaoka |
120a6e |
if (choosedCluster->statistic.elemsCount == 3) break;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#endif
|
|
Toshihiro Shimizu |
890ddd |
|
|
Campbell Barton |
a6cacc |
// Subdivides the cluster chosen in two other clusters.
|
|
Shinya Kitaoka |
120a6e |
Cluster *subcluster1 = new Cluster();
|
|
Shinya Kitaoka |
120a6e |
Cluster *subcluster2 = new Cluster();
|
|
Shinya Kitaoka |
120a6e |
split(subcluster1, subcluster2, eigenVector, choosedCluster);
|
|
Shinya Kitaoka |
120a6e |
assert(subcluster1);
|
|
Shinya Kitaoka |
120a6e |
assert(subcluster2);
|
|
Shinya Kitaoka |
120a6e |
if ((subcluster1->data.size() == 0) || (subcluster2->data.size() == 0))
|
|
Shinya Kitaoka |
120a6e |
break;
|
|
Shinya Kitaoka |
120a6e |
|
|
Campbell Barton |
a6cacc |
// Calculates the new report for 'subcluster1'.
|
|
Shinya Kitaoka |
120a6e |
subcluster1->computeStatistics();
|
|
Shinya Kitaoka |
120a6e |
|
|
Campbell Barton |
a6cacc |
// Calculates the new statistic for 'subcluster2'.
|
|
Shinya Kitaoka |
120a6e |
int j = 0;
|
|
Shinya Kitaoka |
120a6e |
for (; j < 3; ++j) {
|
|
Shinya Kitaoka |
120a6e |
subcluster2->statistic.sumComponents[j] =
|
|
Shinya Kitaoka |
120a6e |
choosedCluster->statistic.sumComponents[j] -
|
|
Shinya Kitaoka |
120a6e |
subcluster1->statistic.sumComponents[j];
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
subcluster2->statistic.sumCoords.x = choosedCluster->statistic.sumCoords.x -
|
|
Shinya Kitaoka |
120a6e |
subcluster1->statistic.sumCoords.x;
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
subcluster2->statistic.sumCoords.y = choosedCluster->statistic.sumCoords.y -
|
|
Shinya Kitaoka |
120a6e |
subcluster1->statistic.sumCoords.y;
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
subcluster2->statistic.elemsCount = choosedCluster->statistic.elemsCount -
|
|
Shinya Kitaoka |
120a6e |
subcluster1->statistic.elemsCount;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#ifdef WITH_ALPHA_IN_STATISTICS
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
subcluster2->statistic.sumAlpha =
|
|
Shinya Kitaoka |
120a6e |
choosedCluster->statistic.sumAlpha - subcluster1->statistic.sumAlpha;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#endif
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
for (j = 0; j < 9; ++j)
|
|
Shinya Kitaoka |
120a6e |
subcluster2->statistic.matrixR[j] = choosedCluster->statistic.matrixR[j] -
|
|
Shinya Kitaoka |
120a6e |
subcluster1->statistic.matrixR[j];
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
subcluster2->computeCovariance();
|
|
Shinya Kitaoka |
120a6e |
|
|
Campbell Barton |
a6cacc |
// Update the appropriate ClusterContainer "clusters", by deleting
|
|
Campbell Barton |
a6cacc |
// the cluster chosen and inserting the two newly created.
|
|
Campbell Barton |
a6cacc |
// So ClusterContainer "cluster" only ever has
|
|
Campbell Barton |
a6cacc |
// the leaves created by the algorithm TSE.
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
Cluster *cluster = *itChoosedCluster;
|
|
Shinya Kitaoka |
120a6e |
assert(cluster);
|
|
Shinya Kitaoka |
120a6e |
cluster->data.clear();
|
|
Shinya Kitaoka |
120a6e |
// clearPointerContainer(cluster->data);
|
|
Shinya Kitaoka |
120a6e |
assert(cluster->data.size() == 0);
|
|
Shinya Kitaoka |
120a6e |
delete cluster;
|
|
Shinya Kitaoka |
120a6e |
clusters.erase(itChoosedCluster);
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
clusters.push_back(subcluster1);
|
|
Shinya Kitaoka |
120a6e |
clusters.push_back(subcluster2);
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
Cluster::Cluster() {}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
Cluster::Cluster(const Cluster &rhs) : statistic(rhs.statistic) {
|
|
Shinya Kitaoka |
120a6e |
ClusterElemContainer::const_iterator it = rhs.data.begin();
|
|
Shinya Kitaoka |
120a6e |
for (; it != rhs.data.end(); ++it) data.push_back(new ClusterElem(**it));
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
Cluster::~Cluster() { clearPointerContainer(data); }
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
void Cluster::computeCovariance() {
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT sumComponentsMatrix[9];
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT sumR = statistic.sumComponents[0];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT sumG = statistic.sumComponents[1];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT sumB = statistic.sumComponents[2];
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
sumComponentsMatrix[0] = sumR * sumR;
|
|
Shinya Kitaoka |
120a6e |
sumComponentsMatrix[1] = sumR * sumG;
|
|
Shinya Kitaoka |
120a6e |
sumComponentsMatrix[2] = sumR * sumB;
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
sumComponentsMatrix[3] = sumComponentsMatrix[1];
|
|
Shinya Kitaoka |
120a6e |
sumComponentsMatrix[4] = sumG * sumG;
|
|
Shinya Kitaoka |
120a6e |
sumComponentsMatrix[5] = sumG * sumB;
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
sumComponentsMatrix[6] = sumComponentsMatrix[2];
|
|
Shinya Kitaoka |
120a6e |
sumComponentsMatrix[7] = sumComponentsMatrix[5];
|
|
Shinya Kitaoka |
120a6e |
sumComponentsMatrix[8] = sumB * sumB;
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT n = (KEYER_FLOAT)statistic.elemsCount;
|
|
Shinya Kitaoka |
120a6e |
assert(n > 0);
|
|
Shinya Kitaoka |
120a6e |
int i = 0;
|
|
Shinya Kitaoka |
120a6e |
for (; i < 9; ++i) {
|
|
Shinya Kitaoka |
120a6e |
statistic.covariance[i] = statistic.matrixR[i] - sumComponentsMatrix[i] / n;
|
|
Shinya Kitaoka |
120a6e |
assert(!ISNAN(statistic.matrixR[i]));
|
|
Shinya Kitaoka |
120a6e |
// assert(statistic.covariance[i] >= 0.0);
|
|
Campbell Barton |
a6cacc |
// numerical instability???
|
|
Shinya Kitaoka |
120a6e |
if (statistic.covariance[i] < 0.0) statistic.covariance[i] = 0.0;
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
void Cluster::insert(ClusterElem *elem) {
|
|
Toshihiro Shimizu |
890ddd |
#ifdef CLUSTER_ELEM_CONTAINER_IS_A_SET
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
data.insert(elem);
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#else
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
data.push_back(elem);
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#endif
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
void Cluster::computeStatistics() {
|
|
Campbell Barton |
a6cacc |
// Initializes the cluster statistics.
|
|
Shinya Kitaoka |
120a6e |
statistic.elemsCount = 0;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
statistic.sumCoords = TPoint(0, 0);
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
int i = 0;
|
|
Shinya Kitaoka |
120a6e |
for (; i < 3; ++i) statistic.sumComponents[i] = 0.0;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
for (i = 0; i < 9; ++i) statistic.matrixR[i] = 0.0;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Campbell Barton |
a6cacc |
// Compute cluster statistics.
|
|
Shinya Kitaoka |
120a6e |
ClusterElemContainer::const_iterator it = data.begin();
|
|
Shinya Kitaoka |
120a6e |
for (; it != data.end(); ++it) {
|
|
Shinya Kitaoka |
120a6e |
const ClusterElem *elem = *it;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#ifdef WITH_ALPHA_IN_STATISTICS
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT alpha = elem->a;
|
|
Toshihiro Shimizu |
890ddd |
#endif
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT r = (KEYER_FLOAT)elem->r;
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT g = (KEYER_FLOAT)elem->g;
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT b = (KEYER_FLOAT)elem->b;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
statistic.sumComponents[0] += r;
|
|
Shinya Kitaoka |
120a6e |
statistic.sumComponents[1] += g;
|
|
Shinya Kitaoka |
120a6e |
statistic.sumComponents[2] += b;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#ifdef WITH_ALPHA_IN_STATISTICS
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
statistic.sumAlpha += alpha;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#endif
|
|
Toshihiro Shimizu |
890ddd |
|
|
Campbell Barton |
a6cacc |
// The first row of the matrix R
|
|
Shinya Kitaoka |
120a6e |
statistic.matrixR[0] += r * r;
|
|
Shinya Kitaoka |
120a6e |
statistic.matrixR[1] += r * g;
|
|
Shinya Kitaoka |
120a6e |
statistic.matrixR[2] += r * b;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Campbell Barton |
a6cacc |
// Second row of the matrix R
|
|
Shinya Kitaoka |
120a6e |
statistic.matrixR[3] += r * g;
|
|
Shinya Kitaoka |
120a6e |
statistic.matrixR[4] += g * g;
|
|
Shinya Kitaoka |
120a6e |
statistic.matrixR[5] += g * b;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Campbell Barton |
a6cacc |
// The third row of the matrix R
|
|
Shinya Kitaoka |
120a6e |
statistic.matrixR[6] += r * b;
|
|
Shinya Kitaoka |
120a6e |
statistic.matrixR[7] += b * g;
|
|
Shinya Kitaoka |
120a6e |
statistic.matrixR[8] += b * b;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
statistic.sumCoords.x += elem->x;
|
|
Shinya Kitaoka |
120a6e |
statistic.sumCoords.y += elem->y;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
++statistic.elemsCount;
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
assert(statistic.elemsCount > 0);
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
computeCovariance();
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
void Cluster::getMeanAxis(KEYER_FLOAT axis[3]) {
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT n = (KEYER_FLOAT)statistic.elemsCount;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#if 1
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
axis[0] = (KEYER_FLOAT)(sqrt(statistic.covariance[0]) / n);
|
|
Shinya Kitaoka |
120a6e |
axis[1] = (KEYER_FLOAT)(sqrt(statistic.covariance[4]) / n);
|
|
Shinya Kitaoka |
120a6e |
axis[2] = (KEYER_FLOAT)(sqrt(statistic.covariance[8]) / n);
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#else
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT I[3];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT J[3];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT K[3];
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
I[0] = statistic.covariance[0];
|
|
Shinya Kitaoka |
120a6e |
I[1] = statistic.covariance[1];
|
|
Shinya Kitaoka |
120a6e |
I[2] = statistic.covariance[2];
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
J[0] = statistic.covariance[3];
|
|
Shinya Kitaoka |
120a6e |
J[1] = statistic.covariance[4];
|
|
Shinya Kitaoka |
120a6e |
J[2] = statistic.covariance[5];
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
K[0] = statistic.covariance[6];
|
|
Shinya Kitaoka |
120a6e |
K[1] = statistic.covariance[7];
|
|
Shinya Kitaoka |
120a6e |
K[2] = statistic.covariance[8];
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT magnitudeI = I[0] * I[0] + I[1] * I[1] + I[2] * I[2];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT magnitudeJ = J[0] * J[0] + J[1] * J[1] + J[2] * I[2];
|
|
Shinya Kitaoka |
120a6e |
KEYER_FLOAT magnitudeK = K[0] * K[0] + K[1] * K[1] + K[2] * I[2];
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
if (magnitudeI >= magnitudeJ && magnitudeI >= magnitudeK) {
|
|
Shinya Kitaoka |
120a6e |
axis[0] = sqrt(I[0] / n);
|
|
Shinya Kitaoka |
120a6e |
axis[1] = sqrt(I[1] / n);
|
|
Shinya Kitaoka |
120a6e |
axis[2] = sqrt(I[2] / n);
|
|
Shinya Kitaoka |
120a6e |
} else if (magnitudeJ >= magnitudeI && magnitudeJ >= magnitudeK) {
|
|
Shinya Kitaoka |
120a6e |
axis[0] = sqrt(J[0] / n);
|
|
Shinya Kitaoka |
120a6e |
axis[1] = sqrt(J[1] / n);
|
|
Shinya Kitaoka |
120a6e |
axis[2] = sqrt(J[2] / n);
|
|
Shinya Kitaoka |
120a6e |
} else if (magnitudeK >= magnitudeI && magnitudeK >= magnitudeJ) {
|
|
Shinya Kitaoka |
120a6e |
axis[0] = sqrt(K[0] / n);
|
|
Shinya Kitaoka |
120a6e |
axis[1] = sqrt(K[1] / n);
|
|
Shinya Kitaoka |
120a6e |
axis[2] = sqrt(K[2] / n);
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#endif
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//#define METODO_USATO_SU_TOONZ46
|
|
Toshihiro Shimizu |
890ddd |
|
|
Campbell Barton |
8c6c57 |
static void buildPaletteForBlendedImages(std::set<tpixel32> &palette,</tpixel32>
|
|
shun-iwasawa |
27b0cf |
const TRaster32P &raster,
|
|
shun-iwasawa |
27b0cf |
int maxColorCount) {
|
|
Shinya Kitaoka |
120a6e |
int lx = raster->getLx();
|
|
Shinya Kitaoka |
120a6e |
int ly = raster->getLy();
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
ClusterContainer clusters;
|
|
Shinya Kitaoka |
120a6e |
Cluster *cluster = new Cluster;
|
|
Shinya Kitaoka |
120a6e |
raster->lock();
|
|
Shinya Kitaoka |
120a6e |
for (int y = 0; y < ly; ++y) {
|
|
Shinya Kitaoka |
120a6e |
TPixel32 *pix = raster->pixels(y);
|
|
Shinya Kitaoka |
120a6e |
for (int x = 0; x < lx; ++x) {
|
|
Shinya Kitaoka |
120a6e |
TPixel32 color = *(pix + x);
|
|
Shinya Kitaoka |
120a6e |
ClusterElem *ce =
|
|
Shinya Kitaoka |
120a6e |
new ClusterElem(color.r, color.g, color.b, (float)(color.m / 255.0));
|
|
Shinya Kitaoka |
120a6e |
cluster->insert(ce);
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
raster->unlock();
|
|
Shinya Kitaoka |
120a6e |
cluster->computeStatistics();
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
clusters.push_back(cluster);
|
|
Shinya Kitaoka |
120a6e |
clusterize(clusters, maxColorCount);
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
palette.clear();
|
|
Shinya Kitaoka |
120a6e |
// palette.reserve( clusters.size());
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
for (UINT i = 0; i < clusters.size(); ++i) {
|
|
Shinya Kitaoka |
120a6e |
ClusterStatistic &stat = clusters[i]->statistic;
|
|
Shinya Kitaoka |
120a6e |
TPixel32 col((int)(stat.sumComponents[0] / stat.elemsCount * 255),
|
|
Shinya Kitaoka |
120a6e |
(int)(stat.sumComponents[1] / stat.elemsCount * 255),
|
|
Shinya Kitaoka |
120a6e |
(int)(stat.sumComponents[2] / stat.elemsCount * 255), 255);
|
|
Shinya Kitaoka |
120a6e |
palette.insert(col);
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
clearPointerContainer(clusters[i]->data);
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
clearPointerContainer(clusters);
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
shun-iwasawa |
dd780b |
#include <qpoint></qpoint>
|
|
shun-iwasawa |
dd780b |
#include <qrect></qrect>
|
|
shun-iwasawa |
dd780b |
#include <qlist></qlist>
|
|
shun-iwasawa |
dd780b |
#include <qmap></qmap>
|
|
shun-iwasawa |
dd780b |
|
|
Shinya Kitaoka |
120a6e |
namespace {
|
|
Toshihiro Shimizu |
890ddd |
#define DISTANCE 3
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
bool inline areNear(const TPixel &c1, const TPixel &c2) {
|
|
Shinya Kitaoka |
120a6e |
if (abs(c1.r - c2.r) > DISTANCE) return false;
|
|
Shinya Kitaoka |
120a6e |
if (abs(c1.g - c2.g) > DISTANCE) return false;
|
|
Shinya Kitaoka |
120a6e |
if (abs(c1.b - c2.b) > DISTANCE) return false;
|
|
Shinya Kitaoka |
120a6e |
if (abs(c1.m - c2.m) > DISTANCE) return false;
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
return true;
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
bool find(const std::set<tpixel32> &palette, const TPixel &color) {</tpixel32>
|
|
Shinya Kitaoka |
120a6e |
std::set<tpixel32>::const_iterator it = palette.begin();</tpixel32>
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
while (it != palette.end()) {
|
|
Shinya Kitaoka |
120a6e |
if (areNear(*it, color)) return true;
|
|
Shinya Kitaoka |
120a6e |
++it;
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Shinya Kitaoka |
120a6e |
return false;
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
shun-iwasawa |
dd780b |
static TPixel32 getPixel(int x, int y, const TRaster32P &raster) {
|
|
shun-iwasawa |
dd780b |
return raster->pixels(y)[x];
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
struct EdgePoint {
|
|
shun-iwasawa |
dd780b |
QPoint pos;
|
|
shun-iwasawa |
dd780b |
enum QUADRANT {
|
|
shun-iwasawa |
dd780b |
RightUpper = 0x01,
|
|
shun-iwasawa |
dd780b |
LeftUpper = 0x02,
|
|
shun-iwasawa |
dd780b |
LeftLower = 0x04,
|
|
shun-iwasawa |
dd780b |
RightLower = 0x08
|
|
shun-iwasawa |
dd780b |
};
|
|
shun-iwasawa |
dd780b |
enum EDGE {
|
|
shun-iwasawa |
dd780b |
UpperEdge = 0x10,
|
|
shun-iwasawa |
dd780b |
LeftEdge = 0x20,
|
|
shun-iwasawa |
dd780b |
LowerEdge = 0x40,
|
|
shun-iwasawa |
dd780b |
RightEdge = 0x80
|
|
shun-iwasawa |
dd780b |
};
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
unsigned char info = 0;
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
EdgePoint(int x, int y) {
|
|
shun-iwasawa |
dd780b |
pos.setX(x);
|
|
shun-iwasawa |
dd780b |
pos.setY(y);
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
// identify the edge pixel by checking if the four neighbor pixels
|
|
shun-iwasawa |
dd780b |
// (distanced by step * 3 pixels) has the same color as the center pixel
|
|
shun-iwasawa |
dd780b |
void initInfo(const TRaster32P &raster, const int step) {
|
|
shun-iwasawa |
dd780b |
int lx = raster->getLx();
|
|
shun-iwasawa |
dd780b |
int ly = raster->getLy();
|
|
shun-iwasawa |
dd780b |
TPixel32 keyColor = getPixel(pos.x(), pos.y(), raster);
|
|
shun-iwasawa |
dd780b |
info = 0;
|
|
shun-iwasawa |
dd780b |
int dist = step * 3;
|
|
shun-iwasawa |
dd780b |
if (pos.y() < ly - dist &&
|
|
shun-iwasawa |
dd780b |
keyColor == getPixel(pos.x(), pos.y() + dist, raster))
|
|
shun-iwasawa |
dd780b |
info = info | UpperEdge;
|
|
shun-iwasawa |
dd780b |
if (pos.x() >= dist &&
|
|
shun-iwasawa |
dd780b |
keyColor == getPixel(pos.x() - dist, pos.y(), raster))
|
|
shun-iwasawa |
dd780b |
info = info | LeftEdge;
|
|
shun-iwasawa |
dd780b |
if (pos.y() >= dist &&
|
|
shun-iwasawa |
dd780b |
keyColor == getPixel(pos.x(), pos.y() - dist, raster))
|
|
shun-iwasawa |
dd780b |
info = info | LowerEdge;
|
|
shun-iwasawa |
dd780b |
if (pos.x() < lx - dist &&
|
|
shun-iwasawa |
dd780b |
keyColor == getPixel(pos.x() + dist, pos.y(), raster))
|
|
shun-iwasawa |
dd780b |
info = info | RightEdge;
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// identify available corners
|
|
shun-iwasawa |
dd780b |
if (info & UpperEdge) {
|
|
shun-iwasawa |
dd780b |
if (info & RightEdge) info = info | RightUpper;
|
|
shun-iwasawa |
dd780b |
if (info & LeftEdge) info = info | LeftUpper;
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
if (info & LowerEdge) {
|
|
shun-iwasawa |
dd780b |
if (info & RightEdge) info = info | RightLower;
|
|
shun-iwasawa |
dd780b |
if (info & LeftEdge) info = info | LeftLower;
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
bool isCorner() {
|
|
shun-iwasawa |
dd780b |
return info & RightUpper || info & LeftUpper || info & RightLower ||
|
|
shun-iwasawa |
dd780b |
info & LeftLower;
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
};
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
struct ColorChip {
|
|
shun-iwasawa |
dd780b |
QRect rect;
|
|
shun-iwasawa |
dd780b |
TPixel32 color;
|
|
shun-iwasawa |
dd780b |
QPoint center;
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
ColorChip(const QPoint &topLeft, const QPoint &bottomRight)
|
|
shun-iwasawa |
dd780b |
: rect(topLeft, bottomRight) {}
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
bool validate(const TRaster32P &raster, const int step) {
|
|
shun-iwasawa |
dd780b |
int lx = raster->getLx();
|
|
shun-iwasawa |
dd780b |
int ly = raster->getLy();
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// just in case - boundary conditions
|
|
shun-iwasawa |
dd780b |
if (!QRect(0, 0, lx - 1, ly - 1).contains(rect)) return false;
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// rectangular must be equal or bigger than 3 * lineWidth
|
|
shun-iwasawa |
dd780b |
if (rect.width() < step * 3 || rect.height() < step * 3) return false;
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// obtain center color
|
|
shun-iwasawa |
dd780b |
center = rect.center();
|
|
shun-iwasawa |
dd780b |
color = getPixel(center.x(), center.y(), raster);
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// it should not be transparent
|
|
shun-iwasawa |
dd780b |
if (color == TPixel::Transparent) return false;
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// rect should be filled with single color
|
|
shun-iwasawa |
dd780b |
raster->lock();
|
|
shun-iwasawa |
dd780b |
for (int y = rect.top() + step; y <= rect.bottom() - 1; y += step) {
|
|
shun-iwasawa |
dd780b |
TPixel *pix = raster->pixels(y) + rect.left() + step;
|
|
shun-iwasawa |
dd780b |
for (int x = rect.left() + step; x <= rect.right() - 1;
|
|
shun-iwasawa |
dd780b |
x += step, pix += step) {
|
|
shun-iwasawa |
dd780b |
if (*pix != color) {
|
|
shun-iwasawa |
dd780b |
raster->unlock();
|
|
shun-iwasawa |
dd780b |
return false;
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
raster->unlock();
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
return true;
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
};
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
bool lowerLeftThan(const EdgePoint &ep1, const EdgePoint &ep2) {
|
|
shun-iwasawa |
dd780b |
if (ep1.pos.y() != ep2.pos.y()) return ep1.pos.y() < ep2.pos.y();
|
|
shun-iwasawa |
dd780b |
return ep1.pos.x() < ep2.pos.x();
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
bool colorChipUpperLeftThan(const ColorChip &chip1, const ColorChip &chip2) {
|
|
shun-iwasawa |
dd780b |
if (chip1.center.y() != chip2.center.y())
|
|
shun-iwasawa |
dd780b |
return chip1.center.y() > chip2.center.y();
|
|
shun-iwasawa |
dd780b |
return chip1.center.x() < chip2.center.x();
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
bool colorChipLowerLeftThan(const ColorChip &chip1, const ColorChip &chip2) {
|
|
shun-iwasawa |
dd780b |
if (chip1.center.y() != chip2.center.y())
|
|
shun-iwasawa |
dd780b |
return chip1.center.y() < chip2.center.y();
|
|
shun-iwasawa |
dd780b |
return chip1.center.x() < chip2.center.x();
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
bool colorChipLeftUpperThan(const ColorChip &chip1, const ColorChip &chip2) {
|
|
shun-iwasawa |
dd780b |
if (chip1.center.x() != chip2.center.x())
|
|
shun-iwasawa |
dd780b |
return chip1.center.x() < chip2.center.x();
|
|
shun-iwasawa |
dd780b |
return chip1.center.y() > chip2.center.y();
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
|
|
Shinya Kitaoka |
120a6e |
} // namespace
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
/*-- 似ている色をまとめて1つのStyleにする --*/
|
|
Shinya Kitaoka |
120a6e |
void TColorUtils::buildPalette(std::set<tpixel32> &palette,</tpixel32>
|
|
Shinya Kitaoka |
120a6e |
const TRaster32P &raster, int maxColorCount) {
|
|
Shinya Kitaoka |
120a6e |
int lx = raster->getLx();
|
|
Shinya Kitaoka |
120a6e |
int ly = raster->getLy();
|
|
Shinya Kitaoka |
120a6e |
int wrap = raster->getWrap();
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
int x, y;
|
|
Shinya Kitaoka |
120a6e |
TPixel old = TPixel::Black;
|
|
Shinya Kitaoka |
120a6e |
int solidColors = 0;
|
|
Shinya Kitaoka |
120a6e |
int count = maxColorCount;
|
|
Shinya Kitaoka |
120a6e |
raster->lock();
|
|
Shinya Kitaoka |
120a6e |
for (y = 1; y < ly - 1 && count > 0; y++) {
|
|
Shinya Kitaoka |
120a6e |
TPixel *pix = raster->pixels(y);
|
|
Shinya Kitaoka |
120a6e |
for (x = 1; x < lx - 1 && count > 0; x++, pix++) {
|
|
Shinya Kitaoka |
120a6e |
TPixel color = *pix;
|
|
Shinya Kitaoka |
120a6e |
if (areNear(color, *(pix - 1)) && areNear(color, *(pix + 1)) &&
|
|
Shinya Kitaoka |
120a6e |
areNear(color, *(pix - wrap)) && areNear(color, *(pix + wrap)) &&
|
|
Shinya Kitaoka |
120a6e |
areNear(color, *(pix - wrap - 1)) &&
|
|
Shinya Kitaoka |
120a6e |
areNear(color, *(pix - wrap + 1)) &&
|
|
Shinya Kitaoka |
120a6e |
areNear(color, *(pix + wrap - 1)) &&
|
|
Shinya Kitaoka |
120a6e |
areNear(color, *(pix + wrap + 1))) {
|
|
Shinya Kitaoka |
120a6e |
solidColors++;
|
|
Shinya Kitaoka |
120a6e |
if (!areNear(*pix, old) && !find(palette, *pix)) {
|
|
Shinya Kitaoka |
120a6e |
old = color;
|
|
Shinya Kitaoka |
120a6e |
count--;
|
|
Shinya Kitaoka |
120a6e |
palette.insert(color);
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
raster->unlock();
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
if (solidColors < lx * ly / 2) {
|
|
Shinya Kitaoka |
120a6e |
palette.clear();
|
|
Shinya Kitaoka |
120a6e |
buildPaletteForBlendedImages(palette, raster, maxColorCount);
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
shun-iwasawa |
dd780b |
//------------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
/*-- 全ての異なるピクセルの色を別のStyleにする --*/
|
|
Shinya Kitaoka |
120a6e |
void TColorUtils::buildPrecisePalette(std::set<tpixel32> &palette,</tpixel32>
|
|
Shinya Kitaoka |
120a6e |
const TRaster32P &raster,
|
|
Shinya Kitaoka |
120a6e |
int maxColorCount) {
|
|
Shinya Kitaoka |
120a6e |
int lx = raster->getLx();
|
|
Shinya Kitaoka |
120a6e |
int ly = raster->getLy();
|
|
Shinya Kitaoka |
120a6e |
int wrap = raster->getWrap();
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
int x, y;
|
|
Shinya Kitaoka |
120a6e |
int count = maxColorCount;
|
|
Shinya Kitaoka |
120a6e |
raster->lock();
|
|
Shinya Kitaoka |
120a6e |
for (y = 1; y < ly - 1 && count > 0; y++) {
|
|
Shinya Kitaoka |
120a6e |
TPixel *pix = raster->pixels(y);
|
|
Shinya Kitaoka |
120a6e |
for (x = 1; x < lx - 1 && count > 0; x++, pix++) {
|
|
Shinya Kitaoka |
120a6e |
if (!find(palette, *pix)) {
|
|
Shinya Kitaoka |
120a6e |
TPixel color = *pix;
|
|
Shinya Kitaoka |
120a6e |
count--;
|
|
Shinya Kitaoka |
120a6e |
palette.insert(color);
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
raster->unlock();
|
|
Shinya Kitaoka |
120a6e |
|
|
Shinya Kitaoka |
120a6e |
/*-- 色数が最大値を超えたら、似ている色をまとめて1つのStyleにする手法を行う
|
|
Shinya Kitaoka |
120a6e |
* --*/
|
|
Shinya Kitaoka |
120a6e |
if (count == 0) {
|
|
Shinya Kitaoka |
120a6e |
palette.clear();
|
|
Shinya Kitaoka |
120a6e |
buildPalette(palette, raster, maxColorCount);
|
|
Shinya Kitaoka |
120a6e |
}
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//------------------------------------------------------------------------------
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
void TColorUtils::buildColorChipPalette(QList<qpair<tpixel32, tpoint="">> &palette,</qpair<tpixel32,>
|
|
shun-iwasawa |
dd780b |
const TRaster32P &raster,
|
|
shun-iwasawa |
dd780b |
int maxColorCount,
|
|
shun-iwasawa |
dd780b |
const TPixel32 &gridColor,
|
|
shun-iwasawa |
dd780b |
const int gridLineWidth,
|
|
shun-iwasawa |
dd780b |
const int colorChipOrder) {
|
|
shun-iwasawa |
dd780b |
int lx = raster->getLx();
|
|
shun-iwasawa |
dd780b |
int ly = raster->getLy();
|
|
shun-iwasawa |
dd780b |
int wrap = raster->getWrap();
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
QList<edgepoint> edgePoints;</edgepoint>
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// search for gridColor in the image
|
|
shun-iwasawa |
dd780b |
int step = gridLineWidth;
|
|
shun-iwasawa |
dd780b |
int x, y;
|
|
shun-iwasawa |
dd780b |
for (y = 0; y < ly; y += step) {
|
|
shun-iwasawa |
dd780b |
TPixel *pix = raster->pixels(y);
|
|
shun-iwasawa |
dd780b |
for (x = 0; x < lx; x += step, pix += step) {
|
|
shun-iwasawa |
dd780b |
if (*pix == gridColor) {
|
|
shun-iwasawa |
dd780b |
EdgePoint edgePoint(x, y);
|
|
shun-iwasawa |
dd780b |
edgePoint.initInfo(raster, step);
|
|
shun-iwasawa |
dd780b |
// store the edgePoint if it can be a corner
|
|
shun-iwasawa |
dd780b |
if (edgePoint.isCorner()) edgePoints.append(edgePoint);
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// std::cout << "edgePoints.count = " << edgePoints.count() << std::endl;
|
|
shun-iwasawa |
dd780b |
// This may be unnecessary
|
|
shun-iwasawa |
dd780b |
qSort(edgePoints.begin(), edgePoints.end(), lowerLeftThan);
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
QList<colorchip> colorChips;</colorchip>
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// make rectangles by serching in the corner points
|
|
shun-iwasawa |
dd780b |
for (int ep0 = 0; ep0 < edgePoints.size(); ep0++) {
|
|
shun-iwasawa |
dd780b |
QMap<edgepoint::quadrant, int=""> corners;</edgepoint::quadrant,>
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// if a point cannot be the first corner, continue
|
|
shun-iwasawa |
dd780b |
if ((edgePoints.at(ep0).info & EdgePoint::RightUpper) == 0) continue;
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// find vertices of rectangle in counter clockwise direction
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// if a point is found which can be the first corner
|
|
shun-iwasawa |
dd780b |
// search for the second corner point at the right side of the first one
|
|
shun-iwasawa |
dd780b |
for (int ep1 = ep0 + 1; ep1 < edgePoints.size(); ep1++) {
|
|
shun-iwasawa |
dd780b |
// end searching at the end of scan line
|
|
shun-iwasawa |
dd780b |
if (edgePoints.at(ep0).pos.y() != edgePoints.at(ep1).pos.y()) break;
|
|
shun-iwasawa |
dd780b |
// if a point cannot be the second corner, continue
|
|
shun-iwasawa |
dd780b |
if ((edgePoints.at(ep1).info & EdgePoint::LeftUpper) == 0) continue;
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// if a point is found which can be the second corner
|
|
shun-iwasawa |
dd780b |
// search for the third corner point at the upper side of the second one
|
|
shun-iwasawa |
dd780b |
for (int ep2 = ep1 + 1; ep2 < edgePoints.size(); ep2++) {
|
|
shun-iwasawa |
dd780b |
// the third point must be at the same x position as the second one
|
|
shun-iwasawa |
dd780b |
if (edgePoints.at(ep1).pos.x() != edgePoints.at(ep2).pos.x()) continue;
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// if a point cannot be the third corner, continue
|
|
shun-iwasawa |
dd780b |
if ((edgePoints.at(ep2).info & EdgePoint::LeftLower) == 0) continue;
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// if a point is found which can be the third corner
|
|
shun-iwasawa |
dd780b |
// search for the forth corner point at the left side of the third one
|
|
shun-iwasawa |
dd780b |
for (int ep3 = ep1 + 1; ep3 < ep2; ep3++) {
|
|
shun-iwasawa |
dd780b |
// if the forth point is found
|
|
shun-iwasawa |
dd780b |
if ((edgePoints.at(ep3).info & EdgePoint::RightLower) &&
|
|
shun-iwasawa |
dd780b |
edgePoints.at(ep0).pos.x() == edgePoints.at(ep3).pos.x() &&
|
|
shun-iwasawa |
dd780b |
edgePoints.at(ep2).pos.y() == edgePoints.at(ep3).pos.y()) {
|
|
shun-iwasawa |
dd780b |
corners[EdgePoint::RightLower] = ep3;
|
|
shun-iwasawa |
dd780b |
break;
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
} // search for ep3 loop
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
if (corners.contains(EdgePoint::RightLower)) {
|
|
shun-iwasawa |
dd780b |
corners[EdgePoint::LeftLower] = ep2;
|
|
shun-iwasawa |
dd780b |
break;
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
} // search for ep2 loop
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
if (corners.contains(EdgePoint::LeftLower)) {
|
|
shun-iwasawa |
dd780b |
corners[EdgePoint::LeftUpper] = ep1;
|
|
shun-iwasawa |
dd780b |
break;
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
} // search for ep1 loop
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// check if all the 4 corner points are found
|
|
shun-iwasawa |
dd780b |
if (corners.contains(EdgePoint::LeftUpper)) {
|
|
shun-iwasawa |
dd780b |
corners[EdgePoint::RightUpper] = ep0;
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
assert(corners.size() == 4);
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// register color chip
|
|
shun-iwasawa |
dd780b |
ColorChip chip(edgePoints.at(corners[EdgePoint::RightUpper]).pos,
|
|
shun-iwasawa |
dd780b |
edgePoints.at(corners[EdgePoint::LeftLower]).pos);
|
|
shun-iwasawa |
dd780b |
if (chip.validate(raster, step)) colorChips.append(chip);
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// remove the coner information from the corner point
|
|
shun-iwasawa |
dd780b |
QMap<edgepoint::quadrant, int="">::const_iterator i = corners.constBegin();</edgepoint::quadrant,>
|
|
shun-iwasawa |
dd780b |
while (i != corners.constEnd()) {
|
|
shun-iwasawa |
dd780b |
edgePoints[i.value()].info & ~i.key();
|
|
shun-iwasawa |
dd780b |
++i;
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
if (colorChips.count() >= maxColorCount) break;
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
// std::cout << "colorChips.count = " << colorChips.count() << std::endl;
|
|
shun-iwasawa |
dd780b |
if (!colorChips.empty()) {
|
|
shun-iwasawa |
dd780b |
// 0:UpperLeft 1:LowerLeft 2:LeftUpper
|
|
shun-iwasawa |
dd780b |
// sort the color chips
|
|
shun-iwasawa |
dd780b |
switch (colorChipOrder) {
|
|
shun-iwasawa |
dd780b |
case 0:
|
|
shun-iwasawa |
dd780b |
qSort(colorChips.begin(), colorChips.end(), colorChipUpperLeftThan);
|
|
shun-iwasawa |
dd780b |
break;
|
|
shun-iwasawa |
dd780b |
case 1:
|
|
shun-iwasawa |
dd780b |
qSort(colorChips.begin(), colorChips.end(), colorChipLowerLeftThan);
|
|
shun-iwasawa |
dd780b |
break;
|
|
shun-iwasawa |
dd780b |
case 2:
|
|
shun-iwasawa |
dd780b |
qSort(colorChips.begin(), colorChips.end(), colorChipLeftUpperThan);
|
|
shun-iwasawa |
dd780b |
break;
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
for (int c = 0; c < colorChips.size(); c++)
|
|
shun-iwasawa |
dd780b |
palette.append(qMakePair(
|
|
shun-iwasawa |
dd780b |
colorChips.at(c).color,
|
|
shun-iwasawa |
dd780b |
TPoint(colorChips.at(c).center.x(), colorChips.at(c).center.y())));
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
}
|
|
shun-iwasawa |
dd780b |
|
|
shun-iwasawa |
dd780b |
//------------------------------------------------------------------------------
|