/* | |
* Copyright (C) 2011 The Android Open Source Project | |
* | |
* Licensed under the Apache License, Version 2.0 (the "License"); | |
* you may not use this file except in compliance with the License. | |
* You may obtain a copy of the License at | |
* | |
* http://www.apache.org/licenses/LICENSE-2.0 | |
* | |
* Unless required by applicable law or agreed to in writing, software | |
* distributed under the License is distributed on an "AS IS" BASIS, | |
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
* See the License for the specific language governing permissions and | |
* limitations under the License. | |
*/ | |
#include <vector> | |
#include <utility> | |
#ifndef FILTERPACK_CALIBRATION_GROUPING_H | |
#define FILTERPACK_CALIBRATION_GROUPING_H | |
// To use the Grouping function, derive one class from Field. | |
// Field class provides the interface for the Grouping function. | |
// FF_ID is the pixel class used to compare values, | |
// != operator must be defined in this class | |
// region number of the pixel | |
typedef std::vector <std::vector<int> > MASK; | |
typedef std::pair<int, int> POS; | |
// FF_ID needs to implement the operator != | |
// bool operator != (const FF_ID &id) | |
template <class FF_ID> | |
class Field { | |
public: | |
int id_no; | |
MASK mask; | |
virtual FF_ID operator () (int y, int x) const =0 ; | |
virtual int getWidth() const = 0; | |
virtual int getHeight() const= 0; | |
virtual ~Field() {} | |
}; | |
template < class FF_ID> | |
void FloodFill(int sx, | |
int sy, | |
int id_no, | |
const FF_ID &id, | |
Field<FF_ID> *pField, | |
POS *new_pos) { | |
std::vector<POS> stack; | |
stack.push_back(POS(sx,sy)); | |
while (stack.size() > 0) { | |
sx = stack.back().first; | |
sy = stack.back().second; | |
stack.pop_back(); | |
// fill the current line | |
int x; | |
for (x = sx-1; x >= 0; x--) | |
{ | |
if (pField->mask[sy][x]!=0) break; | |
if (id != (*pField)(sy,x)) { | |
new_pos->first = x; | |
new_pos->second =sy; | |
break; | |
} | |
pField->mask[sy][x] = id_no; | |
} | |
int startx = x; | |
for (x = sx;x < pField->getWidth(); x++) { | |
if (pField->mask[sy][x]!=0) break; | |
if (id != (*pField)(sy,x)) { | |
new_pos->first = x; | |
new_pos->second =sy; | |
break; | |
} | |
pField->mask[sy][x] = id_no; | |
} | |
int endx = x; | |
if (endx >= pField->getWidth()) endx = pField->getWidth() - 1; | |
if (startx < 0) startx = 0; | |
// push the adjacent spans to the stack | |
if (sy>0) { | |
int bNew = true; | |
for (x = endx; x >= startx; x--) { | |
if (pField->mask[sy-1][x] != 0 || id != (*pField)(sy-1,x) ) { | |
bNew = true; | |
continue; | |
} | |
if (bNew) { | |
stack.push_back( POS(x, sy-1)); | |
bNew = false; | |
} | |
} | |
} | |
if (sy < (pField->getHeight() - 1)) { | |
int bNew = true; | |
for (x = endx; x >= startx; x--) { | |
if (pField->mask[sy+1][x]!=0 || id != (*pField)(sy+1,x)) { | |
bNew = true; | |
continue; | |
} | |
if (bNew) { | |
stack.push_back( POS(x, sy+1)); | |
bNew = false; | |
} | |
} | |
} | |
} | |
} | |
// Group the pixels in Field based on the FF_ID != operator. | |
// All pixels will be labeled from 1. The total number of unique groups(regions) | |
// is (pField->id_no - 1) after the call | |
// The labeasl of the pixels are stored in the mask member of Field. | |
template <class FF_ID> | |
void Grouping(Field <FF_ID> *pField) { | |
int width = pField->getWidth(); | |
int height = pField->getHeight(); | |
pField->mask = MASK(height, std::vector<int> (width, 0) ); | |
FF_ID id; | |
pField->id_no = 1; | |
int sx = width / 2, sy = height / 2; | |
POS new_pos(-1,-1); | |
while (1) { | |
id = (*pField)(sy,sx); | |
int id_no = pField->id_no; | |
new_pos.first = -1; | |
new_pos.second = -1; | |
FloodFill(sx, sy, id_no, id, pField, &new_pos); | |
if (new_pos.first < 0) // no new position found, during the flood fill | |
{ | |
const int kNumOfRetries = 10; | |
// try 10 times for the new unfilled position | |
for (int i = 0; i < kNumOfRetries; i++) { | |
sx = rand() % width; | |
sy = rand() % height; | |
if (pField->mask[sy][sx] == 0) { | |
new_pos.first = sx; | |
new_pos.second = sy; | |
break; | |
} | |
} | |
if (new_pos.first < 0) { // still failed, search the whole image | |
for (int y = 0; y < height && new_pos.first < 0; y++) | |
for (int x = 0; x < width; x++) { | |
if (pField->mask[y][x] == 0) { | |
new_pos.first = x; | |
new_pos.second = y; | |
break; | |
} | |
} | |
} | |
if (new_pos.first < 0) break; // finished | |
} | |
sx = new_pos.first; | |
sy = new_pos.second; | |
pField->id_no++; | |
} | |
} | |
#endif |