LOST 0.0.1
LOST: Open-source Star Tracker
Loading...
Searching...
No Matches
centroiders.cpp
Go to the documentation of this file.
1#include "centroiders.hpp"
2
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6
7#include <algorithm>
8#include <cmath>
9#include <vector>
10#include <unordered_set>
11
12#include "decimal.hpp"
13
14namespace lost {
15
16// DUMMY
17
18std::vector<Star> DummyCentroidAlgorithm::Go(unsigned char *, int imageWidth, int imageHeight) const {
19 std::vector<Star> result;
20
21 unsigned int randomSeed = 123456;
22 for (int i = 0; i < numStars; i++) {
23 result.push_back(Star(rand_r(&randomSeed) % imageWidth, rand_r(&randomSeed) % imageHeight, DECIMAL(10.0)));
24 }
25
26 return result;
27}
28
29// a poorly designed thresholding algorithm
30int BadThreshold(unsigned char *image, int imageWidth, int imageHeight) {
31 //loop through entire array, find sum of magnitudes
32 long totalMag = 0;
33 for (long i = 0; i < imageHeight * imageWidth; i++) {
34 totalMag += image[i];
35 }
36 return (((totalMag/(imageHeight * imageWidth)) + 1) * 15) / 10;
37}
38
39// a more sophisticated thresholding algorithm, not tailored to star images
40int OtsusThreshold(unsigned char *image, int imageWidth, int imageHeight) {
41 // code here, duh
42 long total = imageWidth * imageHeight;
43 //decimal top = 255;
44 decimal sumB = 0;
45 decimal sum1 = 0;
46 decimal wB = 0;
47 decimal maximum = 0;
48 int level = 0;
49 // make the histogram (array length 256)
50 int histogram[256];
51
52 memset(histogram, 0, sizeof(int)*256);
53
54 for (long i = 0; i < total; i++) {
55 histogram[image[i]]++;
56 }
57 for (int i = 0; i < 256; i ++) {
58 sum1 += i * histogram[i];
59 }
60 for (int i = 0; i < 256; i ++) {
61 decimal wF = total - wB;
62 //std::cout << "wF\n" << wB << "\n";
63 //std::cout << "wB\n" << wF << "\n";
64 if (wB > 0 && wF > 0) {
65 decimal mF = (sum1 - sumB) / wF;
66 decimal val = wB * wF * ((sumB / wB) - mF) * ((sumB / wB) - mF);
67 //std::cout << val << "\n";
68 if (val >= maximum) {
69 level = i;
70 maximum = val;
71 }
72 }
73 wB = wB + histogram[i];
74 sumB = sumB + i * histogram[i];
75 }
76 return level;
77}
78
79// a simple, but well tested thresholding algorithm that works well with star images
80int BasicThreshold(unsigned char *image, int imageWidth, int imageHeight,
81 std::vector<unsigned char> *rowMax = nullptr) {
82 unsigned long totalMag = 0;
83 decimal std = 0;
84 long totalPixels = imageHeight * imageWidth;
85 if (rowMax != nullptr) rowMax->assign(imageHeight, 0);
86 for (int y = 0; y < imageHeight; y++) {
87 const unsigned char *row = image + (long)y * imageWidth;
88 unsigned char brightest = 0;
89 for (int x = 0; x < imageWidth; x++) {
90 totalMag += row[x];
91 brightest = std::max(brightest, row[x]);
92 }
93 if (rowMax != nullptr) (*rowMax)[y] = brightest;
94 }
95 decimal mean = DECIMAL(totalMag) / totalPixels;
96 for (long i = 0; i < totalPixels; i++) {
97 std += DECIMAL_POW(image[i] - mean, 2);
98 }
99 std = DECIMAL_SQRT(std / totalPixels);
100 return mean + (std * 5);
101}
102
103// basic thresholding, but do it faster (trade off of some accuracy?)
104int BasicThresholdOnePass(unsigned char *image, int imageWidth, int imageHeight) {
105 unsigned long totalMag = 0;
106 decimal std = 0;
107 decimal sq_totalMag = 0;
108 long totalPixels = imageHeight * imageWidth;
109 for (long i = 0; i < totalPixels; i++) {
110 totalMag += image[i];
111 sq_totalMag += image[i] * image[i];
112 }
113 decimal mean = DECIMAL(totalMag) / totalPixels;
114 decimal variance = (sq_totalMag / totalPixels) - (mean * mean);
115 std = DECIMAL_SQRT(variance);
116 return mean + (std * 5);
117}
118
122 long magSum = 0;
123 int xMin;
124 int xMax;
125 int yMin;
126 int yMax;
127
128 CentroidParams(int x, int y) : xMin(x), xMax(x), yMin(y), yMax(y) {}
129};
130
131std::vector<Star> CenterOfGravityAlgorithm::Go(unsigned char* image, int imageWidth, int imageHeight) const {
132 std::vector<Star> result;
133
134 std::vector<unsigned char> rowMax;
135 int cutoff = BasicThreshold(image, imageWidth, imageHeight, &rowMax);
136 const int offsets[] = {1, -1, imageWidth, -imageWidth};
137 const long n = imageWidth * imageHeight;
138 std::vector<bool> visited(n, false);
139
140 for (int row = 0; row < imageHeight; row++) {
141 if (rowMax[row] < cutoff) continue;
142 const long rowEnd = (long)(row + 1) * imageWidth;
143 for (long i = (long)row * imageWidth; i < rowEnd; i++) {
144 if (image[i] >= cutoff && !visited[i]) {
145 visited[i] = true;
146
147 // If any pixels are on the edge of the image then we don't centroid
148 // this star, in case part of the star is missing
149 bool isValid = true;
150 int centroidSize = 0;
151 std::vector<long> queue = {i};
152 CentroidParams p(i % imageWidth, i / imageWidth);
153
154 while (!queue.empty()) {
155 long ind = queue.back();
156 queue.pop_back();
157 centroidSize++;
158 long x = ind % imageWidth, y = ind / imageWidth;
159 if (x == 0 || x == imageWidth - 1 || y == 0 || y == imageHeight - 1) {
160 isValid = false;
161 }
162
163 p.magSum += image[ind];
164 p.xCoordMagSum += x * image[ind];
165 p.yCoordMagSum += y * image[ind];
166
167 if (x > p.xMax) p.xMax = x;
168 if (x < p.xMin) p.xMin = x;
169 if (y > p.yMax) p.yMax = y;
170 if (y < p.yMin) p.yMin = y;
171
172 for (int offset : offsets) {
173 long ni = ind + offset;
174 if (ni >= 0 && ni < n && std::abs((ni % imageWidth)-x) <= 1 && image[ni] >= cutoff && !visited[ni]) {
175 queue.push_back(ni);
176 visited[ni] = true;
177 }
178 }
179 }
180
181 int xDiameter = (p.xMax - p.xMin) + 1;
182 int yDiameter = (p.yMax - p.yMin) + 1;
183
184 if (isValid && p.magSum > 0) {
185 decimal xCoord = p.xCoordMagSum / DECIMAL(p.magSum);
186 decimal yCoord = p.yCoordMagSum / DECIMAL(p.magSum);
187 result.push_back(Star(xCoord + DECIMAL(0.5), yCoord + DECIMAL(0.5), (xDiameter)/DECIMAL(2.0), (yDiameter)/DECIMAL(2.0), centroidSize));
188 }
189 }
190 }
191 }
192 return result;
193}
194
195//Determines how accurate and how much iteration is done by the IWCoG algorithm,
196//smaller means more accurate and more iterations.
198
200 int xMin;
201 int xMax;
202 int yMin;
203 int yMax;
206 int guess;
208 std::unordered_set<int> checkedIndices;
209};
210
211void IWCoGHelper(IWCoGParams *p, long i, unsigned char *image, int imageWidth, int imageHeight, std::vector<int> *starIndices) {
212 if (i >= 0 && i < imageWidth * imageHeight && image[i] >= p->cutoff && p->checkedIndices.count(i) == 0) {
213 //check if pixel is on the edge of the image, if it is, we dont want to centroid this star
214 if (i % imageWidth == 0 || i % imageWidth == imageWidth - 1 || i / imageWidth == 0 || i / imageWidth == imageHeight - 1) {
215 p->isValid = false;
216 }
217 p->checkedIndices.insert(i);
218 starIndices->push_back(i);
219 if (image[i] > p->maxIntensity) {
220 p->maxIntensity = image[i];
221 p->guess = i;
222 }
223 if (i % imageWidth > p->xMax) {
224 p->xMax = i % imageWidth;
225 } else if (i % imageWidth < p->xMin) {
226 p->xMin = i % imageWidth;
227 }
228 if (i / imageWidth > p->yMax) {
229 p->yMax = i / imageWidth;
230 } else if (i / imageWidth < p->yMin) {
231 p->yMin = i / imageWidth;
232 }
233 if (i % imageWidth != imageWidth - 1) {
234 IWCoGHelper(p, i + 1, image, imageWidth, imageHeight, starIndices);
235 }
236 if (i % imageWidth != 0) {
237 IWCoGHelper(p, i - 1, image, imageWidth, imageHeight, starIndices);
238 }
239 IWCoGHelper(p, i + imageWidth, image, imageWidth, imageHeight, starIndices);
240 IWCoGHelper(p, i - imageWidth, image, imageWidth, imageHeight, starIndices);
241 }
242}
243
244Stars IterativeWeightedCenterOfGravityAlgorithm::Go(unsigned char *image, int imageWidth, int imageHeight) const {
245 IWCoGParams p;
246 std::vector<Star> result;
247 p.cutoff = BasicThreshold(image, imageWidth, imageHeight);
248 for (long i = 0; i < imageHeight * imageWidth; i++) {
249 //check if pixel is part of a "star" and has not been iterated over
250 if (image[i] >= p.cutoff && p.checkedIndices.count(i) == 0) {
251 // TODO: store longs --Mark
252 std::vector<int> starIndices; //indices of the current star
253 p.maxIntensity = 0;
254 int xDiameter = 0;
255 int yDiameter = 0;
256 decimal yWeightedCoordMagSum = 0;
257 decimal xWeightedCoordMagSum = 0;
258 decimal weightedMagSum = 0;
259 decimal fwhm; //fwhm variable
260 decimal standardDeviation;
261 decimal w; //weight value
262
263 p.xMax = i % imageWidth;
264 p.xMin = i % imageWidth;
265 p.yMax = i / imageWidth;
266 p.yMin = i / imageWidth;
267 p.isValid = true;
268
269
270 IWCoGHelper(&p, i, image, imageWidth, imageHeight, &starIndices);
271
272 xDiameter = (p.xMax - p.xMin) + 1;
273 yDiameter = (p.yMax - p.yMin) + 1;
274
275 //calculate fwhm
276 decimal count = 0;
277 for (int j = 0; j < (int) starIndices.size(); j++) {
278 if (image[starIndices.at(j)] > p.maxIntensity / 2) {
279 count++;
280 }
281 }
282 fwhm = DECIMAL_SQRT(count);
283 standardDeviation = fwhm / (DECIMAL(2.0) * DECIMAL_SQRT(DECIMAL(2.0) * DECIMAL_LOG(2.0)));
284 decimal modifiedStdDev = DECIMAL(2.0) * DECIMAL_POW(standardDeviation, 2);
285 // TODO: Why are these decimals? --Mark
286 decimal guessXCoord = (p.guess % imageWidth);
287 decimal guessYCoord = (p.guess / imageWidth);
288 //how much our new centroid estimate changes w each iteration
289 decimal change = INFINITY;
290 int stop = 0;
291 //while we see some large enough change in estimated, maybe make it a global variable
292 while (change > iWCoGMinChange && stop < 100000) {
293 //traverse through star indices, calculate W at each coordinate, add to final coordinate sums
294 yWeightedCoordMagSum = 0;
295 xWeightedCoordMagSum = 0;
296 weightedMagSum = 0;
297 stop++;
298 for (long j = 0; j < (long)starIndices.size(); j++) {
299 //calculate w
300 decimal currXCoord = starIndices.at(j) % imageWidth;
301 decimal currYCoord = starIndices.at(j) / imageWidth;
302 w = p.maxIntensity * DECIMAL_EXP(DECIMAL(-1.0) * ((DECIMAL_POW(currXCoord - guessXCoord, 2) / modifiedStdDev) + (DECIMAL_POW(currYCoord - guessYCoord, 2) / modifiedStdDev)));
303
304 xWeightedCoordMagSum += w * currXCoord * DECIMAL(image[starIndices.at(j)]);
305 yWeightedCoordMagSum += w * currYCoord * DECIMAL(image[starIndices.at(j)]);
306 weightedMagSum += w * DECIMAL(image[starIndices.at(j)]);
307 }
308 decimal xTemp = xWeightedCoordMagSum / weightedMagSum;
309 decimal yTemp = yWeightedCoordMagSum / weightedMagSum;
310
311 change = abs(guessXCoord - xTemp) + abs(guessYCoord - yTemp);
312
313 guessXCoord = xTemp;
314 guessYCoord = yTemp;
315 }
316 if (p.isValid) {
317 result.push_back(Star(guessXCoord + DECIMAL(0.5), guessYCoord + DECIMAL(0.5), xDiameter/DECIMAL(2.0), yDiameter/DECIMAL(2.0), starIndices.size()));
318 }
319 }
320 }
321 return result;
322}
323
324}
Stars Go(unsigned char *image, int imageWidth, int imageHeight) const override
Actually perform the centroid detection.
Stars Go(unsigned char *image, int imageWidth, int imageHeight) const override
Actually perform the centroid detection.
Stars Go(unsigned char *image, int imageWidth, int imageHeight) const override
Actually perform the centroid detection.
A "centroid" detected in an image.
double decimal
Definition decimal.hpp:8
#define DECIMAL_LOG(x)
Definition decimal.hpp:38
#define DECIMAL(x)
Definition decimal.hpp:18
#define DECIMAL_POW(base, power)
Definition decimal.hpp:36
#define DECIMAL_SQRT(x)
Definition decimal.hpp:37
#define DECIMAL_EXP(x)
Definition decimal.hpp:39
LOST starting point.
int OtsusThreshold(unsigned char *image, int imageWidth, int imageHeight)
int BadThreshold(unsigned char *image, int imageWidth, int imageHeight)
std::vector< Star > Stars
void IWCoGHelper(IWCoGParams *p, long i, unsigned char *image, int imageWidth, int imageHeight, std::vector< int > *starIndices)
decimal iWCoGMinChange
int BasicThresholdOnePass(unsigned char *image, int imageWidth, int imageHeight)
int BasicThreshold(unsigned char *image, int imageWidth, int imageHeight, std::vector< unsigned char > *rowMax=nullptr)
CentroidParams(int x, int y)
std::unordered_set< int > checkedIndices