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 17 #include <vector> 18 #include <utility> 19 20 #ifndef FILTERPACK_CALIBRATION_GROUPING_H 21 #define FILTERPACK_CALIBRATION_GROUPING_H 22 23 // To use the Grouping function, derive one class from Field. 24 // Field class provides the interface for the Grouping function. 25 // FF_ID is the pixel class used to compare values, 26 // != operator must be defined in this class 27 // region number of the pixel 28 29 typedef std::vector <std::vector<int> > MASK; 30 typedef std::pair<int, int> POS; 31 // FF_ID needs to implement the operator != 32 // bool operator != (const FF_ID &id) 33 template <class FF_ID> 34 class Field { 35 public: 36 int id_no; 37 MASK mask; 38 virtual FF_ID operator () (int y, int x) const =0 ; 39 virtual int getWidth() const = 0; 40 virtual int getHeight() const= 0; 41 virtual ~Field() {} 42 }; 43 44 template < class FF_ID> 45 void FloodFill(int sx, 46 int sy, 47 int id_no, 48 const FF_ID &id, 49 Field<FF_ID> *pField, 50 POS *new_pos) { 51 std::vector<POS> stack; 52 stack.push_back(POS(sx,sy)); 53 while (stack.size() > 0) { 54 sx = stack.back().first; 55 sy = stack.back().second; 56 stack.pop_back(); 57 58 // fill the current line 59 int x; 60 for (x = sx-1; x >= 0; x--) 61 { 62 if (pField->mask[sy][x]!=0) break; 63 if (id != (*pField)(sy,x)) { 64 new_pos->first = x; 65 new_pos->second =sy; 66 break; 67 } 68 pField->mask[sy][x] = id_no; 69 } 70 int startx = x; 71 for (x = sx;x < pField->getWidth(); x++) { 72 if (pField->mask[sy][x]!=0) break; 73 if (id != (*pField)(sy,x)) { 74 new_pos->first = x; 75 new_pos->second =sy; 76 break; 77 } 78 pField->mask[sy][x] = id_no; 79 } 80 int endx = x; 81 if (endx >= pField->getWidth()) endx = pField->getWidth() - 1; 82 if (startx < 0) startx = 0; 83 // push the adjacent spans to the stack 84 if (sy>0) { 85 int bNew = true; 86 for (x = endx; x >= startx; x--) { 87 if (pField->mask[sy-1][x] != 0 || id != (*pField)(sy-1,x) ) { 88 bNew = true; 89 continue; 90 } 91 if (bNew) { 92 stack.push_back( POS(x, sy-1)); 93 bNew = false; 94 } 95 } 96 } 97 if (sy < (pField->getHeight() - 1)) { 98 int bNew = true; 99 for (x = endx; x >= startx; x--) { 100 if (pField->mask[sy+1][x]!=0 || id != (*pField)(sy+1,x)) { 101 bNew = true; 102 continue; 103 } 104 if (bNew) { 105 stack.push_back( POS(x, sy+1)); 106 bNew = false; 107 } 108 } 109 } 110 } 111 } 112 113 // Group the pixels in Field based on the FF_ID != operator. 114 // All pixels will be labeled from 1. The total number of unique groups(regions) 115 // is (pField->id_no - 1) after the call 116 // The labeasl of the pixels are stored in the mask member of Field. 117 118 template <class FF_ID> 119 void Grouping(Field <FF_ID> *pField) { 120 int width = pField->getWidth(); 121 int height = pField->getHeight(); 122 pField->mask = MASK(height, std::vector<int> (width, 0) ); 123 124 FF_ID id; 125 pField->id_no = 1; 126 int sx = width / 2, sy = height / 2; 127 POS new_pos(-1,-1); 128 while (1) { 129 id = (*pField)(sy,sx); 130 int id_no = pField->id_no; 131 new_pos.first = -1; 132 new_pos.second = -1; 133 FloodFill(sx, sy, id_no, id, pField, &new_pos); 134 if (new_pos.first < 0) // no new position found, during the flood fill 135 { 136 const int kNumOfRetries = 10; 137 // try 10 times for the new unfilled position 138 for (int i = 0; i < kNumOfRetries; i++) { 139 sx = rand() % width; 140 sy = rand() % height; 141 if (pField->mask[sy][sx] == 0) { 142 new_pos.first = sx; 143 new_pos.second = sy; 144 break; 145 } 146 } 147 if (new_pos.first < 0) { // still failed, search the whole image 148 for (int y = 0; y < height && new_pos.first < 0; y++) 149 for (int x = 0; x < width; x++) { 150 if (pField->mask[y][x] == 0) { 151 new_pos.first = x; 152 new_pos.second = y; 153 break; 154 } 155 } 156 } 157 if (new_pos.first < 0) break; // finished 158 } 159 sx = new_pos.first; 160 sy = new_pos.second; 161 pField->id_no++; 162 } 163 } 164 165 #endif 166
