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;
~Field()41 virtual ~Field() {}
42 };
43
44 template < class FF_ID>
FloodFill(int sx,int sy,int id_no,const FF_ID & id,Field<FF_ID> * pField,POS * new_pos)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>
Grouping(Field<FF_ID> * pField)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