1 /* 2 * Copyright (C) 2011 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 #define LOG_NDEBUG 0 17 18 #define LOG_TAG "ColorCheckerTest" 19 #include <utils/Log.h> 20 #include <utils/Timers.h> 21 #include <cmath> 22 #include <string> 23 24 #include "vec2.h" 25 #include "vec3.h" 26 #include "colorcheckertest.h" 27 28 const float GAMMA_CORRECTION = 2.2f; 29 const float COLOR_ERROR_THRESHOLD = 200.f; 30 ColorCheckerTest::~ColorCheckerTest() { 31 ALOGV("Deleting color checker test handler"); 32 33 if (mImage != NULL) { 34 delete mImage; 35 } 36 ALOGV("Image deleted"); 37 38 int numHorizontalLines = mCandidateColors.size(); 39 int numVerticalLines = mCandidateColors[0].size(); 40 41 for (int i = 0; i < numHorizontalLines; ++i) { 42 for (int j = 0; j < numVerticalLines; ++j) { 43 if (mCandidateColors[i][j] != NULL) { 44 delete mCandidateColors[i][j]; 45 } 46 if (mCandidatePositions[i][j] != NULL) { 47 delete mCandidatePositions[i][j]; 48 } 49 } 50 } 51 ALOGV("Candidates deleted!"); 52 53 for (int i = 0; i < 4; ++i) { 54 for (int j = 0; j < 6; ++j) { 55 if (mMatchPositions[i][j] != NULL) { 56 delete mMatchPositions[i][j]; 57 } 58 if (mReferenceColors[i][j] != NULL) { 59 delete mReferenceColors[i][j]; 60 } 61 if (mMatchColors[i][j] != NULL) { 62 delete mMatchColors[i][j]; 63 } 64 } 65 } 66 } 67 68 // Adds a new image to the test handler. 69 void ColorCheckerTest::addTestingImage(TestingImage* inputImage) { 70 if (mImage != NULL) { 71 delete mImage; 72 } 73 mImage = NULL; 74 ALOGV("Original image deleted"); 75 mImage = inputImage; 76 77 if ((mImage->getHeight() == getDebugHeight()) && 78 (mImage->getWidth() == getDebugWidth())) { 79 copyDebugImage(getDebugHeight(), getDebugWidth(), mImage->getImage()); 80 } 81 } 82 83 void ColorCheckerTest::processData() { 84 mSuccess = false; 85 initializeRefColor(); 86 edgeDetection(); 87 } 88 89 void ColorCheckerTest::initializeRefColor() { 90 mReferenceColors.resize(4, std::vector<Vec3i*>(6, NULL)); 91 mMatchPositions.resize(4, std::vector<Vec2f*>(6, NULL)); 92 mMatchColors.resize(4, std::vector<Vec3f*>(6, NULL)); 93 mMatchRadius.resize(4, std::vector<float>(6, 0.f)); 94 95 mReferenceColors[0][0]= new Vec3i(115, 82, 68); 96 mReferenceColors[0][1]= new Vec3i(194, 150, 130); 97 mReferenceColors[0][2]= new Vec3i(98, 122, 157); 98 mReferenceColors[0][3]= new Vec3i(87, 108, 67); 99 mReferenceColors[0][4]= new Vec3i(133, 128, 177); 100 mReferenceColors[0][5]= new Vec3i(103, 189, 170); 101 mReferenceColors[1][0]= new Vec3i(214, 126, 44); 102 mReferenceColors[1][1]= new Vec3i(80, 91, 166); 103 mReferenceColors[1][2]= new Vec3i(193, 90, 99); 104 mReferenceColors[1][3]= new Vec3i(94, 60, 108); 105 mReferenceColors[1][4]= new Vec3i(157, 188, 64); 106 mReferenceColors[1][5]= new Vec3i(224, 163, 46); 107 mReferenceColors[2][0]= new Vec3i(56, 61, 150); 108 mReferenceColors[2][1]= new Vec3i(70, 148, 73); 109 mReferenceColors[2][2]= new Vec3i(175, 54, 60); 110 mReferenceColors[2][3]= new Vec3i(231, 199, 31); 111 mReferenceColors[2][4]= new Vec3i(187, 86, 149); 112 mReferenceColors[2][5]= new Vec3i(8, 133, 161); 113 mReferenceColors[3][0]= new Vec3i(243, 243, 242); 114 mReferenceColors[3][1]= new Vec3i(200, 200, 200); 115 mReferenceColors[3][2]= new Vec3i(160, 160, 160); 116 mReferenceColors[3][3]= new Vec3i(122, 122, 121); 117 mReferenceColors[3][4]= new Vec3i(85, 85, 85); 118 mReferenceColors[3][5]= new Vec3i(52, 52, 52); 119 } 120 121 void ColorCheckerTest::edgeDetection() { 122 int width = mImage->getWidth(); 123 int height = mImage->getHeight(); 124 125 bool* edgeMap = new bool[height * width]; 126 unsigned char* grayImage = new unsigned char[height * width]; 127 128 // If the image is a color image and can be converted to a luminance layer 129 if (mImage->rgbToGrayScale(grayImage)) { 130 float* gradientMap = new float[height * width * 2]; 131 132 // Computes the gradient image on the luminance layer. 133 computeGradient(grayImage, gradientMap); 134 135 float* gradientMagnitude = new float[height * width]; 136 int* gradientDirectionInt = new int[height * width]; 137 float* gradientDirection = new float[height * width]; 138 139 // Computes the absolute gradient of the image without padding. 140 for (int i = 1; i < height - 1; ++i) { 141 for (int j = 1; j < width - 1; ++j) { 142 gradientMagnitude[i * width + j] = 143 sqrt(gradientMap[(i * width + j) * 2] * 144 gradientMap[(i * width + j) * 2] + 145 gradientMap[(i * width + j ) * 2 + 1] * 146 gradientMap[(i * width + j ) * 2 + 1]); 147 148 // Computes the gradient direction of the image. 149 if (gradientMap[(i * width + j) * 2] == 0 ) { 150 // If the vertical gradient is 0, the edge is horizontal 151 // Mark the gradient direction as 90 degrees. 152 gradientDirectionInt[i * width + j] = 2; 153 gradientDirection[i * width + j] = 90.0f; 154 } else { 155 // Otherwise the atan operation is valid and can decide 156 // the gradient direction of the edge. 157 float gradient = atan(gradientMap[(i * width + j) * 2 + 1] 158 / gradientMap[(i * width + j) * 2]) 159 / (M_PI / 4); 160 161 gradientDirection[i * width + j] = gradient * 45.0f; 162 163 // Maps the gradient direction to 4 major directions with 164 // 0 mapped to up and 2 mapped to right. 165 if (gradient - floor(gradient) > 0.5) { 166 gradientDirectionInt[i * width + j] = 167 (static_cast<int>(ceil(gradient)) + 4) % 4; 168 } else { 169 gradientDirectionInt[i * width + j] = 170 (static_cast<int>(floor(gradient)) + 4) % 4; 171 } 172 } 173 } 174 } 175 176 // Compute a boolean map to show whether a pixel is on the edge. 177 for (int i = 1; i < height - 1; ++i) { 178 for (int j = 1; j < width - 1; ++j) { 179 edgeMap[i * width + j] = false; 180 181 switch (gradientDirectionInt[i * width + j]) { 182 case 0: 183 // If the gradient points rightwards, the pixel is 184 // on an edge if it has a larger absolute gradient than 185 // pixels on its left and right sides. 186 if ((gradientMagnitude[i * width + j] >= 187 gradientMagnitude[i * width + j + 1]) && 188 (gradientMagnitude[i * width + j] >= 189 gradientMagnitude[i * width + j - 1])) { 190 edgeMap[i * width + j] = true; 191 } 192 break; 193 case 1: 194 // If the gradient points right-downwards, the pixel is 195 // on an edge if it has a larger absolute gradient than 196 // pixels on its upper left and bottom right sides. 197 if ((gradientMagnitude[i * width + j] >= 198 gradientMagnitude[(i + 1) * width + j + 1]) && 199 (gradientMagnitude[i * width + j] >= 200 gradientMagnitude[(i - 1) * width + j - 1])) { 201 edgeMap[i * width + j] = true; 202 } 203 break; 204 case 2: 205 // If the gradient points upwards, the pixel is 206 // on an edge if it has a larger absolute gradient than 207 // pixels on its up and down sides. 208 if ((gradientMagnitude[i * width + j] >= 209 gradientMagnitude[(i + 1) * width + j]) && 210 (gradientMagnitude[i * width + j] >= 211 gradientMagnitude[(i - 1) * width + j])) { 212 edgeMap[i * width + j] = true; 213 } 214 break; 215 case 3: 216 // If the gradient points right-upwards, the pixel is 217 // on an edge if it has a larger absolute gradient than 218 // pixels on its bottom left and upper right sides. 219 if ((gradientMagnitude[i * width + j] >= 220 gradientMagnitude[(i - 1) * width + j + 1]) && 221 (gradientMagnitude[i * width + j] >= 222 gradientMagnitude[(i + 1) * width + j - 1])) { 223 edgeMap[i * width + j] = true; 224 } 225 } 226 227 } 228 } 229 230 houghLineDetection(edgeMap, gradientMagnitude, gradientDirection); 231 232 // Cleans up 233 delete[] gradientMap; 234 delete[] gradientDirectionInt; 235 delete[] gradientMagnitude; 236 delete[] gradientDirection; 237 238 } else { 239 ALOGE("Not a color image!"); 240 } 241 242 delete[] edgeMap; 243 delete[] grayImage; 244 } 245 246 // Runs the hough voting algorithm to find the grid of the color checker 247 // with the edge map, gradient direction and gradient magnitude as inputs. 248 void ColorCheckerTest::houghLineDetection(bool* edgeMap, 249 float* gradientMagnitude, 250 float* gradientDirection) { 251 // Constructs a graph for Hough voting. The vertical axis counts the vote 252 // for a certain angle. The horizontal axis counts the vote for the distance 253 // of a line from the origin of the image. 254 int houghHeight = 180; 255 int houghWidth = 200; 256 int houghCounts[houghHeight][houghWidth]; 257 int houghSum[houghHeight][houghWidth]; 258 259 int** houghVote; 260 houghVote = new int*[180]; 261 for (int i = 0; i < 180; ++i) { 262 houghVote[i] = new int[200]; 263 } 264 265 for (int i = 0; i < houghHeight; ++i) { 266 for (int j = 0; j < houghWidth; ++j) { 267 houghCounts[i][j] = 0; 268 houghVote[i][j] = 0; 269 houghSum[i][j] = 0; 270 } 271 } 272 273 // Vectors to record lines in two orthogonal directions. 274 // Each line is represented by its direction and its distance to the origin. 275 std::vector<std::vector<int> > verticalLines; 276 std::vector<std::vector<int> > horizontalLines; 277 float radius; 278 int height = mImage->getHeight(); 279 int width = mImage->getWidth(); 280 281 // Processes the signicant edge pixels and cast vote for the corresponding 282 // edge passing this pixel. 283 for (int i = 1; i < height - 1; ++i) { 284 for (int j = 1; j < width - 1; ++j) { 285 // Sets threashold for the gradient magnitude to discount noises 286 if (edgeMap[i * width + j] && 287 (gradientMagnitude[i * width + j] > 15)) { 288 int shiftedAngle; 289 290 // Shifts angles for 45 degrees so the vertical and horizontal 291 // direction is mapped to 45 and 135 degrees to avoid padding. 292 // This uses the assumption that the color checker is placed 293 // roughly parallel to the image boarders. So that the edges 294 // at the angle of 45 will be rare. 295 shiftedAngle = (static_cast<int>( 296 -gradientDirection[i * width + j]) + 225 % 180); 297 float shiftedAngleRad = static_cast<float>(shiftedAngle) 298 * M_PI / 180.0f; 299 300 // Computes the distance of the line from the origin. 301 float a, b; 302 a = static_cast<float>(i - j) / sqrt(2.0f); 303 b = static_cast<float>(i + j) / sqrt(2.0f); 304 radius = a * sin(shiftedAngleRad) - b * cos(shiftedAngleRad); 305 306 // Adds one vote for the line. The line's angle is shifted by 307 // 45 degrees to avoid avoid padding for the vertical lines, 308 // which is more common than diagonal lines. The line's 309 // distance is mapped to [0, 200] from [-200, 200]. 310 ++houghCounts[shiftedAngle][static_cast<int>((radius / 2.0f) + 311 100.0f)]; 312 313 drawPoint(i, j, Vec3i(255, 255, 255)); 314 } 315 } 316 } 317 318 int houghAngleSum[houghHeight]; 319 int primaryVerticalAngle, primaryHorizontalAngle; 320 int max1 = 0; 321 int max2 = 0; 322 323 // Looking for the two primary angles of the lines. 324 for (int i = 5; i < houghHeight - 5; ++i) { 325 houghAngleSum[i] = 0; 326 for (int j = 0; j < houghWidth; ++j) { 327 for (int l = -5; l <= 5; ++l) { 328 houghSum[i][j] += houghCounts[i + l][j]; 329 } 330 houghAngleSum[i] += houghSum[i][j]; 331 } 332 333 if ((i < houghHeight / 2) && (houghAngleSum[i] > max1)) { 334 max1 = houghAngleSum[i]; 335 primaryVerticalAngle = i; 336 } else if ((i > houghHeight / 2) && (houghAngleSum[i] > max2)) { 337 max2 = houghAngleSum[i]; 338 primaryHorizontalAngle = i; 339 } 340 } 341 342 ALOGV("Primary angles are %d, %d", 343 primaryVerticalAngle, primaryHorizontalAngle); 344 345 int angle; 346 347 // For each primary angle, look for the highest voted lines. 348 for (int k = 0; k < 2; ++k) { 349 if (k == 0) { 350 angle = primaryVerticalAngle; 351 } else { 352 angle = primaryHorizontalAngle; 353 } 354 355 std::vector<int> line(2); 356 for (int j = 2; j < houghWidth - 2; ++j) { 357 houghVote[angle][j] = houghSum[angle][j]; 358 houghSum[angle][j] = 0; 359 } 360 361 // For each radius, average the vote with nearby ones. 362 for (int j = 2; j < houghWidth - 2; ++j) { 363 for (int m = -2; m <= 2; ++m) { 364 houghSum[angle][j] += houghVote[angle][j + m]; 365 } 366 } 367 368 bool isCandidate[houghWidth]; 369 370 // Find whether a lines is a candidate by rejecting the ones that have 371 // lower vote than others in the neighborhood. 372 for (int j = 2; j < houghWidth - 2; ++j) { 373 isCandidate[j] = true; 374 for (int m = -2; ((isCandidate[j]) && (m <= 2)); ++m) { 375 if ((houghSum[angle][j] < 20) || 376 (houghSum[angle][j] < houghSum[angle][j + m])) { 377 isCandidate[j] = false; 378 } 379 } 380 } 381 382 int iter1 = 0; 383 int iter2 = 0; 384 int count = 0; 385 386 // Finds the lines that are not too close to each other and add to the 387 // detected lines. 388 while (iter2 < houghWidth) { 389 while ((!isCandidate[iter2]) && (iter2 < houghWidth)) { 390 ++iter2; 391 } 392 if ((isCandidate[iter2]) && (iter2 - iter1 < 5)) { 393 iter1 = (iter2 + iter1) / 2; 394 ++iter2; 395 } else { 396 line[0] = angle; 397 line[1] = (iter1 - 100) * 2; 398 if (iter1 != 0) { 399 if (k == 0) { 400 verticalLines.push_back(line); 401 Vec3i color(verticalLines.size() * 20, 0, 0); 402 drawLine(line[0], line[1], color); 403 } else { 404 horizontalLines.push_back(line); 405 Vec3i color(0, horizontalLines.size() * 20, 0); 406 drawLine(line[0], line[1], color); 407 } 408 } 409 iter1 = iter2; 410 ++iter2; 411 ALOGV("pushing back line %d %d", line[0], line[1]); 412 } 413 } 414 } 415 416 ALOGV("Numbers of lines in each direction is %d, %d", 417 verticalLines.size(), horizontalLines.size()); 418 419 for (int i = 0; i < 180; ++i) { 420 delete[] houghVote[i]; 421 } 422 delete[] houghVote; 423 424 findCheckerBoards(verticalLines, horizontalLines); 425 } 426 427 // Computes the gradient in both x and y direction of a layer 428 void ColorCheckerTest::computeGradient(unsigned char* layer, 429 float* gradientMap) { 430 int width = mImage->getWidth(); 431 int height = mImage->getHeight(); 432 433 // Computes the gradient in the whole image except the image boarders. 434 for (int i = 1; i < height - 1; ++i) { 435 for (int j = 1; j < width - 1; ++j) { 436 gradientMap[(i * width + j) * 2] = 437 0.5f * (layer[i * width + j + 1] - 438 layer[i * width + j - 1]); 439 gradientMap[(i * width + j) * 2 + 1] = 440 0.5f * (layer[(i + 1) * width + j] - 441 layer[(i - 1) * width + j]); 442 } 443 } 444 } 445 446 // Tries to find the checker boards with the highest voted lines 447 void ColorCheckerTest::findCheckerBoards( 448 std::vector<std::vector<int> > verticalLines, 449 std::vector<std::vector<int> > horizontalLines) { 450 ALOGV("Start looking for Color checker"); 451 452 int numHorizontalLines = mCandidateColors.size(); 453 int numVerticalLines; 454 if (numHorizontalLines > 0) { 455 numVerticalLines = mCandidateColors[0].size(); 456 for (int i = 0; i < numHorizontalLines; ++i) { 457 for (int j = 0; j < numVerticalLines; ++j) { 458 if (mCandidateColors[i][j] != NULL) { 459 delete mCandidateColors[i][j]; 460 } 461 if (mCandidatePositions[i][j] != NULL) { 462 delete mCandidatePositions[i][j]; 463 } 464 } 465 mCandidateColors[i].clear(); 466 mCandidatePositions[i].clear(); 467 } 468 } 469 mCandidateColors.clear(); 470 mCandidatePositions.clear(); 471 472 ALOGV("Candidates deleted!"); 473 474 numVerticalLines = verticalLines.size(); 475 numHorizontalLines = horizontalLines.size(); 476 Vec2f pointUpperLeft; 477 Vec2f pointBottomRight; 478 479 mCandidateColors.resize(numHorizontalLines - 1); 480 mCandidatePositions.resize(numHorizontalLines - 1); 481 482 for (int i = numVerticalLines - 1; i >= 1; --i) { 483 for (int j = 0; j < numHorizontalLines - 1; ++j) { 484 // Finds the upper left and bottom right corner of each rectangle 485 // formed by two neighboring highest voted lines. 486 pointUpperLeft = findCrossing(verticalLines[i], horizontalLines[j]); 487 pointBottomRight = findCrossing(verticalLines[i - 1], 488 horizontalLines[j + 1]); 489 490 Vec3i* color = new Vec3i(); 491 Vec2f* pointCenter = new Vec2f(); 492 // Verifies if they are separated by a reasonable distance. 493 if (verifyPointPair(pointUpperLeft, pointBottomRight, 494 pointCenter, color)) { 495 mCandidatePositions[j].push_back(pointCenter); 496 mCandidateColors[j].push_back(color); 497 ALOGV("Color at (%d, %d) is (%d, %d, %d)", j, i,color->r(), color->g(), color->b()); 498 499 } else { 500 mCandidatePositions[j].push_back(NULL); 501 mCandidateColors[j].push_back(NULL); 502 delete color; 503 delete pointCenter; 504 } 505 } 506 } 507 508 ALOGV("Candidates Number (%d, %d)", mCandidateColors.size(), mCandidateColors[0].size()); 509 // Verifies whether the current line candidates form a valid color checker. 510 verifyColorGrid(); 511 } 512 513 // Returns the corssing point of two lines given the lines. 514 Vec2f ColorCheckerTest::findCrossing(std::vector<int> line1, 515 std::vector<int> line2) { 516 Vec2f crossingPoint; 517 float r1 = static_cast<float>(line1[1]); 518 float r2 = static_cast<float>(line2[1]); 519 float ang1, ang2; 520 float y1, y2; 521 522 ang1 = static_cast<float>(line1[0]) / 180.0f * M_PI; 523 ang2 = static_cast<float>(line2[0]) / 180.0f * M_PI; 524 525 float x, y; 526 x = (r1 * cos(ang2) - r2 * cos(ang1)) / sin(ang1 - ang2); 527 y = (r1 * sin(ang2) - r2 * sin(ang1)) / sin(ang1 - ang2); 528 529 crossingPoint.set((x + y) / sqrt(2.0), (y - x) / sqrt(2.0)); 530 531 //ALOGV("Crosspoint at (%f, %f)", crossingPoint.x(), crossingPoint.y()); 532 return crossingPoint; 533 } 534 535 // Verifies whether two opposite corners on a quadrilateral actually can be 536 // the two corners of a color checker. 537 bool ColorCheckerTest::verifyPointPair(Vec2f pointUpperLeft, 538 Vec2f pointBottomRight, 539 Vec2f* pointCenter, 540 Vec3i* color) { 541 bool success = true; 542 543 /** 5 and 30 are the threshold tuned for resolution 640*480*/ 544 if ((pointUpperLeft.x() < 0) || 545 (pointUpperLeft.x() >= mImage->getHeight()) || 546 (pointUpperLeft.y() < 0) || 547 (pointUpperLeft.y() >= mImage->getWidth()) || 548 (pointBottomRight.x() < 0) || 549 (pointBottomRight.x() >= mImage->getHeight()) || 550 (pointBottomRight.y() < 0) || 551 (pointBottomRight.y() >= mImage->getWidth()) || 552 (abs(pointUpperLeft.x() - pointBottomRight.x()) <= 5) || 553 (abs(pointUpperLeft.y() - pointBottomRight.y()) <= 5) || 554 (abs(pointUpperLeft.x() - pointBottomRight.x()) >= 30) || 555 (abs(pointUpperLeft.y() - pointBottomRight.y()) >= 30)) { 556 557 // If any of the quadrilateral corners are out of the image or if 558 // the distance between them are too large or too big, the quadrilateral 559 // could not be one of the checkers 560 success = false; 561 } else { 562 // Find the checker center if the corners of the rectangle meet criteria 563 pointCenter->set((pointUpperLeft.x() + pointBottomRight.x()) / 2.0f, 564 (pointUpperLeft.y() + pointBottomRight.y()) / 2.0f); 565 color->set(mImage->getPixelValue(*pointCenter).r(), 566 mImage->getPixelValue(*pointCenter).g(), 567 mImage->getPixelValue(*pointCenter).b()); 568 ALOGV("Color at (%f, %f) is (%d, %d, %d)", pointCenter->x(), pointCenter->y(),color->r(), color->g(), color->b()); 569 } 570 return success; 571 } 572 573 // Verifies the color checker centers and finds the match between the detected 574 // color checker and the reference MacBeth color checker 575 void ColorCheckerTest::verifyColorGrid() { 576 ALOGV("Start looking for Color Grid"); 577 int numHorizontalLines = mCandidateColors.size(); 578 int numVerticalLines = mCandidateColors[0].size(); 579 bool success = false; 580 581 // Computes the standard deviation of one row/column of the proposed color 582 // checker. Discards the row/column if the std is below a threshold. 583 for (int i = 0; i < numHorizontalLines; ++i) { 584 Vec3f meanColor(0.f, 0.f, 0.f); 585 int numNonZero = 0; 586 587 for (int j = 0; j < numVerticalLines; ++j) { 588 if (mCandidateColors[i][j] != NULL) { 589 ALOGV("candidate color (%d, %d) is (%d, %d, %d)", i, j, mCandidateColors[i][j]->r(), mCandidateColors[i][j]->g(), mCandidateColors[i][j]->b()); 590 591 meanColor = meanColor + (*mCandidateColors[i][j]); 592 ++numNonZero; 593 } 594 } 595 if (numNonZero > 0) { 596 meanColor = meanColor / numNonZero; 597 } 598 ALOGV("Mean color for vertical direction computed!"); 599 600 float std = 0; 601 for (int j = 0; j < numVerticalLines; ++j) { 602 if (mCandidateColors[i][j] != NULL) { 603 std += mCandidateColors[i][j]->squareDistance<float>(meanColor); 604 } 605 } 606 if (numNonZero > 0) { 607 std = sqrt(std / (3 * numNonZero)); 608 } 609 ALOGV("st. deviation for the %d dir1 is %d", i, static_cast<int>(std)); 610 611 if ((std <= 30) && (numNonZero > 1)) { 612 for (int j = 0; j < numVerticalLines; ++j) { 613 if (mCandidateColors[i][j] != NULL) { 614 delete mCandidateColors[i][j]; 615 mCandidateColors[i][j] = NULL; 616 } 617 } 618 } 619 } 620 621 // Discards the column/row of the color checker if the std is below a 622 // threshold. 623 for (int j = 0; j < numVerticalLines; ++j) { 624 Vec3f meanColor(0.f, 0.f, 0.f); 625 int numNonZero = 0; 626 627 for (int i = 0; i < numHorizontalLines; ++i) { 628 if (mCandidateColors[i][j] != NULL) { 629 meanColor = meanColor + (*mCandidateColors[i][j]); 630 ++numNonZero; 631 } 632 } 633 if (numNonZero > 0) { 634 meanColor = meanColor / numNonZero; 635 } 636 637 float std = 0; 638 for (int i = 0; i < numHorizontalLines; ++i) { 639 if (mCandidateColors[i][j] != NULL) { 640 std += mCandidateColors[i][j]->squareDistance<float>(meanColor); 641 } 642 } 643 if (numNonZero > 0) { 644 std = sqrt(std / (3 * numNonZero)); 645 } 646 647 ALOGV("st. deviation for the %d dir2 is %d", j, static_cast<int>(std)); 648 649 if ((std <= 30) && (numNonZero > 1)) { 650 for (int i = 0; i < numHorizontalLines; ++i) { 651 if (mCandidateColors[i][j] != NULL) { 652 delete mCandidateColors[i][j]; 653 mCandidateColors[i][j] = NULL; 654 } 655 } 656 } 657 } 658 659 for (int i = 0; i < numHorizontalLines; ++i) { 660 for (int j = 0; j < numVerticalLines; ++j) { 661 if (mCandidateColors[i][j] != NULL) { 662 ALOGV("position (%d, %d) is at (%f, %f) with color (%d, %d, %d)", 663 i, j, 664 mCandidatePositions[i][j]->x(), 665 mCandidatePositions[i][j]->y(), 666 mCandidateColors[i][j]->r(), 667 mCandidateColors[i][j]->g(), 668 mCandidateColors[i][j]->b()); 669 } else { 670 ALOGV("position (%d, %d) is 0", i, j); 671 } 672 } 673 } 674 675 // Finds the match between the detected color checker and the reference 676 // MacBeth color checker. 677 int rowStart = 0; 678 int rowEnd = 0; 679 680 // Loops until all dectected color checker has been processed. 681 while (!success) { 682 int columnStart = 0; 683 int columnEnd = 0; 684 bool isRowStart = false; 685 bool isRowEnd = true; 686 687 // Finds the row start of the next block of detected color checkers. 688 while ((!isRowStart) && (rowStart < numHorizontalLines)) { 689 for (int j = 0; j < numVerticalLines; ++j) { 690 if (mCandidateColors[rowStart][j] != NULL) { 691 isRowStart = true; 692 } 693 } 694 ++rowStart; 695 } 696 rowStart--; 697 rowEnd = rowStart; 698 ALOGV("rowStart is %d", rowStart); 699 700 // Finds the row end of the next block of detected color checkers. 701 while ((isRowEnd) && (rowEnd < numHorizontalLines)) { 702 isRowEnd = false; 703 for (int j = 0; j < numVerticalLines; ++j) { 704 if (mCandidateColors[rowEnd][j] != NULL) { 705 isRowEnd= true; 706 } 707 } 708 if (isRowEnd) { 709 ++rowEnd; 710 } 711 } 712 if ((!isRowEnd) && isRowStart) { 713 rowEnd--; 714 } 715 if ((isRowEnd) && (rowEnd == numHorizontalLines)) { 716 rowEnd--; 717 isRowEnd = false; 718 } 719 ALOGV("rowEnd is %d", rowEnd); 720 721 // Matches color checkers between the start row and the end row. 722 bool successVertical = false; 723 724 while (!successVertical) { 725 bool isColumnEnd = true; 726 bool isColumnStart = false; 727 728 // Finds the start column of the next block of color checker 729 while ((!isColumnStart) && (columnStart < numVerticalLines)) { 730 if (mCandidateColors[rowStart][columnStart] != NULL) { 731 isColumnStart = true; 732 } 733 ++columnStart; 734 } 735 columnStart--; 736 columnEnd = columnStart; 737 738 // Finds the end column of the next block of color checker 739 while ((isColumnEnd) && (columnEnd < numVerticalLines)) { 740 isColumnEnd = false; 741 if (mCandidateColors[rowStart][columnEnd] != NULL) 742 isColumnEnd = true; 743 if (isColumnEnd) { 744 ++columnEnd; 745 } 746 } 747 748 if ((!isColumnEnd) && isColumnStart) { 749 columnEnd--; 750 } 751 if ((isColumnEnd) && (columnEnd == numVerticalLines)) { 752 columnEnd--; 753 isColumnEnd = false; 754 } 755 756 // Finds the best match on the MacBeth reference color checker for 757 // the continuous block of detected color checker 758 if (isRowStart && (!isRowEnd) && 759 isColumnStart && (!isColumnEnd)) { 760 findBestMatch(rowStart, rowEnd, columnStart, columnEnd); 761 } 762 ALOGV("FindBestMatch for %d, %d, %d, %d", rowStart, 763 rowEnd, columnStart, columnEnd); 764 765 // If the column search finishes, go out of the loop 766 if (columnEnd >= numVerticalLines - 1) { 767 successVertical = true; 768 } else { 769 columnStart = columnEnd + 1; 770 } 771 } 772 ALOGV("Continuing to search for direction 1"); 773 774 // If the row search finishes, go out of the loop 775 if (rowEnd >= numHorizontalLines - 1) { 776 success = true; 777 } else { 778 rowStart = rowEnd + 1; 779 } 780 } 781 782 for (int i = 0; i < 4; ++i) { 783 for (int j = 0; j < 6; ++j) { 784 if (mMatchPositions[i][j] != NULL) { 785 ALOGV("Reference Match position for (%d, %d) is (%f, %f)", i, j, 786 mMatchPositions[i][j]->x(), mMatchPositions[i][j]->y()); 787 } 788 } 789 } 790 791 fillRefColorGrid(); 792 } 793 794 // Finds the best match on the MacBeth color checker for the continuous block of 795 // detected color checkers bounded by row i1, row i2 and column j1 and column j2 796 // Assumes that the subsample is less than 4*6. 797 void ColorCheckerTest::findBestMatch(int i1, int i2, int j1, int j2) { 798 int numHorizontalGrid = i2 - i1 + 1; 799 int numVerticalGrid = j2 - j1 + 1; 800 801 if (((numHorizontalGrid > 1) || (numVerticalGrid > 1)) && 802 (numHorizontalGrid <= 4) && (numVerticalGrid <= 6)) { 803 ALOGV("i1, j2, j1, j2 is %d, %d, %d, %d", i1, i2, j1, j2); 804 float minError; 805 float error = 0.f; 806 int horizontalMatch, verticalMatch; 807 808 // Finds the match start point where the error is minimized. 809 for (int i = 0; i < numHorizontalGrid; ++i) { 810 for (int j = 0; j < numVerticalGrid; ++j) { 811 if (mCandidateColors[i1 + i][j1 + j] != NULL) { 812 error += mCandidateColors[i1 + i][j1 + j]->squareDistance<int>( 813 *mReferenceColors[i][j]); 814 } 815 } 816 } 817 ALOGV("Error is %f", error); 818 minError = error; 819 horizontalMatch = 0; 820 verticalMatch = 0; 821 822 for (int i = 0; i <= 4 - numHorizontalGrid; ++i) { 823 for (int j = 0; j <= 6 - numVerticalGrid; ++j) { 824 error = 0.f; 825 826 for (int id = 0; id < numHorizontalGrid; ++id) { 827 for (int jd = 0; jd < numVerticalGrid; ++jd) { 828 if (mCandidateColors[i1 + id][j1 + jd] != NULL) { 829 error += mCandidateColors[i1 + id][j1 + jd]-> 830 squareDistance<int>( 831 *mReferenceColors[i + id][j + jd]); 832 } 833 } 834 } 835 836 if (error < minError) { 837 minError = error; 838 horizontalMatch = i; 839 verticalMatch = j; 840 } 841 ALOGV("Processed %d, %d and error is %f", i, j, error ); 842 } 843 } 844 845 for (int id = 0; id < numHorizontalGrid; ++id) { 846 for (int jd = 0; jd < numVerticalGrid; ++jd) { 847 if (mCandidatePositions[i1 + id][j1 + jd] != NULL) { 848 mMatchPositions[horizontalMatch + id][verticalMatch + jd] = 849 new Vec2f(mCandidatePositions[i1 + id][j1 + jd]->x(), 850 mCandidatePositions[i1 + id][j1 + jd]->y()); 851 } 852 } 853 } 854 ALOGV("Grid match starts at %d, %d", horizontalMatch, verticalMatch); 855 } 856 } 857 858 // Finds the boundary of a color checker by its color similarity to the center. 859 // Also predicts the location of unmatched checkers. 860 void ColorCheckerTest::fillRefColorGrid() { 861 int rowStart = 0; 862 int columnStart = 0; 863 bool foundStart = true; 864 865 for (int i = 0; (i < 4) && foundStart; ++i) { 866 for (int j = 0; (j < 6) && foundStart; ++j) { 867 if (mMatchPositions[i][j] != NULL) { 868 rowStart = i; 869 columnStart = j; 870 foundStart = false; 871 } 872 } 873 } 874 ALOGV("First match found at (%d, %d)", rowStart, columnStart); 875 876 float rowDistance, columnDistance; 877 rowDistance = 0; 878 columnDistance = 0; 879 int numRowGrids = 0; 880 int numColumnGrids = 0; 881 882 for (int i = rowStart; i < 4; ++i) { 883 for (int j = columnStart; j < 6; ++j) { 884 if (mMatchPositions[i][j] != NULL) { 885 if (i > rowStart) { 886 ++numRowGrids; 887 rowDistance += (mMatchPositions[i][j]->x() - 888 mMatchPositions[rowStart][columnStart]->x()) / 889 static_cast<float>(i - rowStart); 890 } 891 if (j > columnStart) { 892 ++numColumnGrids; 893 columnDistance += (mMatchPositions[i][j]->y() - 894 mMatchPositions[rowStart][columnStart]->y()) / 895 static_cast<float>(j - columnStart); 896 } 897 } 898 } 899 } 900 901 if ((numRowGrids > 0) && (numColumnGrids > 0)) { 902 rowDistance = rowDistance / numRowGrids; 903 columnDistance = columnDistance / numColumnGrids; 904 ALOGV("delta is %f, %f", rowDistance, columnDistance); 905 906 for (int i = 0; i < 4; ++i) { 907 for (int j = 0 ; j < 6; ++j) { 908 if (mMatchPositions[i][j] == NULL) { 909 mMatchPositions[i][j] = new Vec2f( 910 mMatchPositions[rowStart][columnStart]->x() + 911 (i - rowStart) * rowDistance, 912 mMatchPositions[rowStart][columnStart]->y() + 913 (j - columnStart) * columnDistance); 914 } 915 } 916 } 917 for (int i = 0; i < 4; ++i) { 918 for (int j = 0; j < 6; ++j) { 919 float radius = 0; 920 Vec3i color = mImage->getPixelValue(*mMatchPositions[i][j]); 921 Vec3f meanColor(0.f , 0.f, 0.f); 922 923 int numPixels = 0; 924 for (int ii = static_cast<int>(mMatchPositions[i][j]->x() - 925 rowDistance/2); 926 ii <= static_cast<int>(mMatchPositions[i][j]->x() + 927 rowDistance/2); 928 ++ii) { 929 for (int jj = static_cast<int>(mMatchPositions[i][j]->y() - 930 columnDistance/2); 931 jj <= static_cast<int>(mMatchPositions[i][j]->y() + 932 columnDistance/2); 933 ++jj) { 934 if ((ii >= 0) && (ii < mImage->getHeight()) && 935 (jj >= 0) && (jj < mImage->getWidth())) { 936 Vec3i pixelColor = mImage->getPixelValue(ii,jj); 937 float error = color.squareDistance<int>(pixelColor); 938 939 if (error < COLOR_ERROR_THRESHOLD) { 940 drawPoint(ii, jj, *mReferenceColors[i][j]); 941 meanColor = meanColor + pixelColor; 942 numPixels++; 943 Vec2i pixelPosition(ii, jj); 944 945 if (pixelPosition.squareDistance<float>( 946 *mMatchPositions[i][j]) > radius) { 947 radius = pixelPosition.squareDistance<float>( 948 *mMatchPositions[i][j]); 949 } 950 } 951 } 952 } 953 } 954 955 /** Computes the radius of the checker. 956 * The above computed radius is the squared distance to the 957 * furthest point with a matching color. To be conservative, we 958 * only consider an area with radius half of the above computed 959 * value. Since radius is computed as a squared root, the one 960 * that will be recorded is 1/4 of the above computed value. 961 */ 962 mMatchRadius[i][j] = radius / 4.f; 963 mMatchColors[i][j] = new Vec3f(meanColor / numPixels); 964 965 ALOGV("Reference color at (%d, %d) is (%d, %d, %d)", i, j, 966 mReferenceColors[i][j]->r(), 967 mReferenceColors[i][j]->g(), 968 mReferenceColors[i][j]->b()); 969 ALOGV("Average color at (%d, %d) is (%f, %f, %f)", i, j, 970 mMatchColors[i][j]->r(), 971 mMatchColors[i][j]->g(), 972 mMatchColors[i][j]->b()); 973 ALOGV("Radius is %f", mMatchRadius[i][j]); 974 } 975 } 976 977 mSuccess = true; 978 } 979 } 980
