fork download
copy 
  1. #include <stddef.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <math.h>
  5. #include <assert.h>
  6. #include <float.h>
  7. #include <string.h>
  8. #include <opencv2/opencv.hpp>
  9. #include <time.h>
  10.  
  11. #define DEBUG 0
  12. #define max(a,b) (a)>(b)?(a):(b)
  13. #define min(a,b) (a)>(b)?(b):(a)
  14.  
  15. #define DELAYED_ANODE_ALLOC		1
  16. #define HQUEUE_COST_AMORTIZE	1
  17.  
  18. #define NULL_LEVELROOT		0xffffffff
  19. #define ANODE_CANDIDATE		0xfffffffe
  20.  
  21. #define dimg_idx_v(pidx) ((pidx)<<1)
  22. #define dimg_idx_h(pidx) ((pidx)<<1)+1
  23.  
  24. #define LEFT_AVAIL(pidx,width)			(((pidx) % (width)) != 0)
  25. #define RIGHT_AVAIL(pidx,width)			(((pidx) % (width)) != ((width) - 1))
  26. #define UP_AVAIL(pidx,width)				((pidx) > ((width) - 1))
  27. #define DOWN_AVAIL(pidx,width,imgsz)		((pidx) < (imgsz) - (width))
  28.  
  29. #define HQUEUE_ELEMENT_SIZE		4
  30. #define LEVELROOT_ELEMENT_SIZE	8
  31. #define DHIST_ELEMENT_SIZE		4
  32. #define DIMG_ELEMENT_SIZE		1
  33. #define ISVISITED_ELEMENT_SIZE	1
  34.  
  35. typedef unsigned char uint8;
  36. typedef unsigned short uint16;
  37. typedef unsigned long uint32;
  38. typedef unsigned long long uint64;
  39.  
  40. typedef uint8 pixel; //designed for 8-bit images
  41.  
  42. typedef struct HQueue
  43. {
  44. 	uint32 *queue, *bottom, *cur;
  45. 	uint64 qsize;
  46. 	uint32 min_level, max_level;
  47. }HQueue;
  48.  
  49.  
  50. HQueue* hqueue_new(uint64 qsize, uint32 *dhist, uint32 dhistsize)
  51. {
  52. 	uint32 i;
  53. 	HQueue* hqueue = (HQueue*)malloc(sizeof(HQueue));
  54. 	hqueue->queue = (uint32*)malloc((size_t)qsize * sizeof(uint32));
  55. 	hqueue->bottom = (uint32*)malloc((size_t)(dhistsize + 1) * sizeof(uint32));
  56. 	hqueue->cur = (uint32*)malloc((size_t)(dhistsize + 1) * sizeof(uint32));
  57.  
  58. 	hqueue->qsize = qsize;
  59. 	hqueue->min_level = hqueue->max_level = dhistsize;
  60.  
  61.  
  62. 	int sum_hist = 0;
  63. 	for (i = 0; i < dhistsize; i++)
  64. 	{
  65. 		hqueue->bottom[i] = hqueue->cur[i] = sum_hist;
  66. 		sum_hist += dhist[i];
  67. 	}
  68. 	hqueue->bottom[dhistsize] = 0;
  69. 	hqueue->cur[dhistsize] = 1;
  70.  
  71. 	return hqueue;
  72. }
  73.  
  74. void hqueue_free(HQueue* hqueue)
  75. {
  76. 	free(hqueue->queue);
  77. 	free(hqueue->bottom);
  78. 	free(hqueue->cur);
  79. 	free(hqueue);
  80. }
  81.  
  82. inline void hqueue_push(HQueue* hqueue, uint32 newidx, uint32 level)
  83. {
  84. 	hqueue->min_level = min(level, hqueue->min_level);
  85. #if DEBUG
  86. 	assert(level < hqueue->max_level);
  87. 	assert(hqueue->cur[level] < hqueue->qsize);
  88. #endif
  89. 	hqueue->queue[hqueue->cur[level]++] = newidx;
  90. }
  91.  
  92. inline uint32 hqueue_pop(HQueue* hqueue)
  93. {
  94. 	return hqueue->queue[--hqueue->cur[hqueue->min_level]];
  95. }
  96.  
  97. inline void hqueue_find_min_level(HQueue* hqueue)
  98. {
  99. 	while (hqueue->bottom[hqueue->min_level] == hqueue->cur[hqueue->min_level])
  100. 		hqueue->min_level++;
  101. }
  102.  
  103. typedef struct AlphaNode
  104. {
  105. 	uint32 area;
  106. 	uint8 level;  /* alpha of flat zone */
  107. 	double sumPix;
  108. 	pixel minPix;
  109. 	pixel maxPix;
  110. 	uint32 parentidx;
  111. } AlphaNode;
  112.  
  113. typedef struct AlphaTree
  114. {
  115. 	uint32 maxSize;
  116. 	uint32 curSize;
  117. 	uint32 height, width, channel;
  118. 	AlphaNode* node;
  119. 	uint32* parentAry;
  120. } AlphaTree;
  121.  
  122.  
  123. inline void connectPix2Node(uint32* parentAry, uint32 pidx, uint8 pix_val, AlphaNode* pNode, uint32 iNode)
  124. {
  125. 	parentAry[pidx] = iNode;
  126. 	pNode->area++;
  127. 	pNode->maxPix = max(pNode->maxPix, pix_val);
  128. 	pNode->minPix = min(pNode->minPix, pix_val);
  129. 	pNode->sumPix += pix_val;
  130. }
  131.  
  132. inline void connectNode2Node(AlphaNode* pPar, uint32 iPar, AlphaNode* pNode)
  133. {
  134. 	pNode->parentidx = iPar;
  135. 	pPar->area += pNode->area;
  136. 	pPar->maxPix = max(pNode->maxPix, pPar->maxPix);
  137. 	pPar->minPix = min(pNode->minPix, pPar->minPix);
  138. 	pPar->sumPix += pNode->sumPix;
  139. }
  140.  
  141. void compute_dimg(uint8* dimg, uint32* dhist, uint8* img, uint32 height, uint32 width, uint32 channel)
  142. {
  143.  
  144. 	uint32 dimgidx, imgidx, stride_w = width, i, j, ch;
  145. 	if (channel == 1)
  146. 	{
  147. 		imgidx = dimgidx = 0;
  148. 		for (i = 0; i < height - 1; i++)
  149. 		{
  150. 			for (j = 0; j < width - 1; j++)
  151. 			{
  152. 				dimg[dimgidx] = (uint8)abs((int)img[imgidx + stride_w] - (int)img[imgidx]);
  153. 				dhist[dimg[dimgidx++]]++;
  154. 				dimg[dimgidx] = (uint8)abs((int)img[imgidx + 1] - (int)img[imgidx]);
  155. 				dhist[dimg[dimgidx++]]++;
  156. 				imgidx++;
  157. 			}
  158. 			dimg[dimgidx] = (uint8)abs((int)img[imgidx + stride_w] - (int)img[imgidx]);
  159. 			dhist[dimg[dimgidx++]]++;
  160. 			dimgidx++;
  161. 			imgidx++;
  162. 		}
  163. 		for (j = 0; j < width - 1; j++)
  164. 		{
  165. 			dimgidx++;
  166. 			dimg[dimgidx] = (uint8)abs((int)img[imgidx + 1] - (int)img[imgidx]);
  167. 			dhist[dimg[dimgidx++]]++;
  168. 			imgidx++;
  169. 		}
  170. 	}
  171. 	else
  172. 	{
  173. 		for (ch = 0; ch < channel; ch++)
  174. 		{
  175. 			imgidx = dimgidx = 0;
  176. 			for (i = 0; i < height - 1; i++)
  177. 			{
  178. 				for (j = 0; j < width - 1; j++)
  179. 				{
  180. 					dimg[dimgidx++] = max(dimg[dimgidx], (uint8)abs((int)img[imgidx + stride_w] - (int)img[imgidx])); // use Lmax dissim
  181. 					if (ch == channel - 1)
  182. 						dhist[dimg[dimgidx - 1]]++;
  183. 					dimg[dimgidx++] = max(dimg[dimgidx], (uint8)abs((int)img[imgidx + 1] - (int)img[imgidx]));
  184. 					if (ch == channel - 1)
  185. 						dhist[dimg[dimgidx - 1]]++;
  186. 					imgidx++;
  187. 				}
  188. 				dimg[dimgidx++] = max(dimg[dimgidx], (uint8)abs((int)img[imgidx + stride_w] - (int)img[imgidx]));
  189. 				if (ch == channel - 1)
  190. 					dhist[dimg[dimgidx - 1]]++;
  191. 				dimgidx++;
  192. 				imgidx++;
  193. 			}
  194. 			for (j = 0; j < width - 1; j++)
  195. 			{
  196. 				dimgidx++;
  197. 				dimg[dimgidx++] = max(dimg[dimgidx], (uint8)abs((int)img[imgidx + 1] - (int)img[imgidx]));
  198. 				if (ch == channel - 1)
  199. 					dhist[dimg[dimgidx - 1]]++;
  200. 				imgidx++;
  201. 			}
  202. 			img += width * height;
  203. 		}
  204. 	}
  205. }
  206. inline uint32 NewAlphaNode(AlphaTree* tree, uint8 level)
  207. {
  208. 	AlphaNode *pNew = tree->node + tree->curSize;
  209. 	pNew->level = level;
  210. 	pNew->minPix = (pixel)-1;
  211. 	pNew->minPix = 0;
  212. 	pNew->sumPix = 0.0;
  213. 	pNew->parentidx = 0;
  214. 	pNew->area = 0;
  215.  
  216. 	return tree->curSize++;
  217. }
  218.  
  219. inline uint8 is_visited(uint8* isVisited, uint32 p)
  220. {
  221. 	return (isVisited[p>>3] >> (p & 7)) & 1;
  222. }
  223.  
  224. inline void visit(uint8* isVisited, uint32 p)
  225. {
  226. 	isVisited[p >> 3] = isVisited[p >> 3] | (1 << (p & 7));
  227. }
  228.  
  229.  
  230. void Flood(AlphaTree* tree, uint8* img, uint32 height, uint32 width, uint32 channel)
  231. {
  232. 	uint32 imgsize, dimgsize, nredges, max_level, current_level, next_level, x0, p, dissim;
  233. 	uint32 numlevels;
  234. 	HQueue* hqueue;
  235. 	uint32 *dhist;
  236. 	pixel *dimg;
  237. 	uint32 iChild, *levelroot;
  238. 	uint8 *isVisited;
  239. 	AlphaNode *pNode;
  240. 	uint32 *pParentAry;
  241.  
  242. 	imgsize = width * height;
  243. 	nredges = width * (height - 1) + (width - 1) * height;
  244. 	dimgsize = 2 * width * height; //To make indexing easier
  245. 	numlevels = 1 << (8 * sizeof(uint8));
  246.  
  247. 	//tmp_mem_size = imgsize * ISVISITED_ELEMENT_SIZE + (nredges + 1) * (HQUEUE_ELEMENT_SIZE)+dimgsize * (DIMG_ELEMENT_SIZE)+ 
  248. 	//numlevels * (LEVELROOT_ELEMENT_SIZE + DHIST_ELEMENT_SIZE + sizeof(hqueue_index)) + sizeof(hqueue_index) + LEVELROOT_ELEMENT_SIZE;
  249.  
  250.  
  251. 	dhist = (uint32*)malloc((size_t)numlevels * sizeof(uint32));
  252. 	dimg = (pixel*)malloc((size_t)dimgsize * sizeof(pixel));
  253. 	levelroot = (uint32*)malloc((uint32)(numlevels + 1) * LEVELROOT_ELEMENT_SIZE);
  254. 	isVisited = (uint8*)malloc((size_t)(imgsize >> 3));
  255. 	for (p = 0; p < numlevels; p++)
  256. 		levelroot[p] = NULL_LEVELROOT;
  257. 	memset(dhist, 0, (size_t)numlevels * sizeof(uint32));
  258. 	memset(isVisited, 0, (size_t)(imgsize >> 3));
  259.  
  260. 	max_level = (uint8)(numlevels - 1);
  261.  
  262. 	compute_dimg(dimg, dhist, img, height, width, channel);
  263. 	dhist[max_level]++;
  264. 	hqueue = hqueue_new(nredges + 1, dhist, numlevels);
  265.  
  266. 	tree->height = height;
  267. 	tree->width = width;
  268. 	tree->channel = channel;
  269. 	tree->curSize = 0;
  270. 	tree->maxSize = imgsize + 1;//tree size estimation
  271. 	tree->parentAry = (uint32*)malloc((size_t)imgsize * sizeof(uint32));
  272. 	tree->node = (AlphaNode*)malloc((size_t)tree->maxSize * sizeof(AlphaNode));
  273. 	pNode = tree->node;
  274. 	pParentAry = tree->parentAry;
  275.  
  276. 	levelroot[max_level + 1] = NewAlphaNode(tree, (uint8)max_level);
  277. 	pNode[levelroot[max_level + 1]].parentidx = levelroot[max_level + 1];
  278.  
  279. 	current_level = max_level;
  280. 	x0 = imgsize >> 1;
  281. 	hqueue_push(hqueue, x0, current_level);
  282.  
  283. 	iChild = levelroot[max_level + 1];
  284. 	while (current_level <= max_level)
  285. 	{
  286. 		while (hqueue->min_level <= current_level)
  287. 		{
  288. 			p = hqueue_pop(hqueue);
  289. 			if (is_visited(isVisited, p))
  290. 			{
  291. 				hqueue_find_min_level(hqueue);
  292. 				continue;
  293. 			}
  294. 			visit(isVisited, p);
  295. #if !HQUEUE_COST_AMORTIZE
  296. 			hqueue_find_min_level();
  297. #endif
  298.  
  299. 			if (LEFT_AVAIL(p, width) && !is_visited(isVisited, p - 1))
  300. 			{
  301. 				dissim = (uint32)dimg[dimg_idx_h(p - 1)];
  302. 				hqueue_push(hqueue, p - 1, dissim);
  303. 				if (levelroot[dissim] == NULL_LEVELROOT)
  304. #if DELAYED_ANODE_ALLOC
  305. 					levelroot[dissim] = ANODE_CANDIDATE;
  306. #else
  307. 					levelroot[dissim] = NewAlphaNode(tree, (uint8)dissim);
  308. #endif
  309. 			}
  310. 			if (RIGHT_AVAIL(p, width) && !is_visited(isVisited, p + 1))
  311. 			{
  312. 				dissim = (uint32)dimg[dimg_idx_h(p)];
  313. 				hqueue_push(hqueue, p + 1, dissim);
  314. 				if (levelroot[dissim] == NULL_LEVELROOT)
  315. #if DELAYED_ANODE_ALLOC
  316. 					levelroot[dissim] = ANODE_CANDIDATE;
  317. #else
  318. 					levelroot[dissim] = NewAlphaNode(tree, (uint8)dissim);
  319. #endif
  320. 			}
  321. 			if (UP_AVAIL(p, width) && !is_visited(isVisited, p - width))
  322. 			{
  323. 				dissim = (uint32)dimg[dimg_idx_v(p - width)];
  324. 				hqueue_push(hqueue, p - width, dissim);
  325. 				if (levelroot[dissim] == NULL_LEVELROOT)
  326. #if DELAYED_ANODE_ALLOC
  327. 					levelroot[dissim] = ANODE_CANDIDATE;
  328. #else
  329. 					levelroot[dissim] = NewAlphaNode(tree, (uint8)dissim);
  330. #endif
  331. 			}
  332. 			if (DOWN_AVAIL(p, width, imgsize) && !is_visited(isVisited, p + width))
  333. 			{
  334. 				dissim = (uint32)dimg[dimg_idx_v(p)];
  335. 				hqueue_push(hqueue, p + width, dissim);
  336. 				if (levelroot[dissim] == NULL_LEVELROOT)
  337. #if DELAYED_ANODE_ALLOC
  338. 					levelroot[dissim] = ANODE_CANDIDATE;
  339. #else
  340. 					levelroot[dissim] = NewAlphaNode(tree, (uint8)dissim);
  341. #endif
  342. 			}
  343.  
  344. 			if (current_level > hqueue->min_level)
  345. 				current_level = hqueue->min_level;
  346. #if HQUEUE_COST_AMORTIZE
  347. 			else
  348. 				hqueue_find_min_level(hqueue);
  349. #endif
  350.  
  351. #if DELAYED_ANODE_ALLOC
  352. 			if (levelroot[current_level] == ANODE_CANDIDATE)
  353. 				levelroot[current_level] = NewAlphaNode(tree, (uint8)current_level);
  354. #endif
  355. 			connectPix2Node(pParentAry, p, img[p], pNode + levelroot[current_level], levelroot[current_level]);
  356. 		}
  357. //		if(tree->curSize > 22051838 && (tree->curSize))
  358. 	//		printf("curSize: %d\n",tree->curSize);
  359. 		//Redundant node removal
  360. 		if (pNode[iChild].parentidx == levelroot[current_level] &&
  361. 			pNode[levelroot[current_level]].area == pNode[iChild].area)
  362. 		{
  363. 			levelroot[current_level] = iChild;
  364. 			tree->curSize--;
  365.  
  366. 			memset((uint8*)(pNode + tree->curSize), 0, sizeof(AlphaNode));
  367. 		}
  368.  
  369. 		next_level = current_level + 1;
  370. 		while (next_level <= max_level && (levelroot[next_level] == NULL_LEVELROOT))
  371. 			next_level++;
  372. 		if (levelroot[next_level] == ANODE_CANDIDATE)
  373. 			levelroot[next_level] = NewAlphaNode(tree, (uint8)next_level);
  374. 		connectNode2Node(pNode + levelroot[next_level], levelroot[next_level], pNode + levelroot[current_level]);
  375. 		iChild = levelroot[current_level];
  376. 		levelroot[current_level] = NULL_LEVELROOT;
  377. 		current_level = next_level;
  378. 	}
  379. 	hqueue_free(hqueue);
  380. 	free(dhist);
  381. 	free(dimg);
  382. 	free(levelroot);
  383. 	free(isVisited);
  384. }
  385.  
  386.  
  387. void BuildAlphaTree(AlphaTree* tree, uint8 *img, uint32 height, uint32 width, uint32 channel)
  388. {
  389. 	Flood(tree, img, height, width, channel);
  390. }
  391.  
  392. void DeleteAlphaTree(AlphaTree* tree)
  393. {
  394. 	free(tree->parentAry);
  395. 	free(tree->node);
  396. 	free(tree);
  397. }
  398.  
  399. int main(int argc, char **argv)
  400. {	
  401. 	cv::String str1("butterfly.jpg");
  402. 	cv::Mat img = imread(str1, cv::IMREAD_ANYCOLOR);
  403. 	AlphaTree tree;
  404.  
  405. 		//	cv::String str("C:/jwryu/RUG/2018/AlphaTree/imgdata/Colour_imgs/16578511714_6eaef1c5bb_o.jpg");
  406. //	cv::Mat img = imread(str, CV_LOAD_IMAGE_COLOR);
  407. //	cv::String str("C:/jwryu/RUG/2018/AlphaTree/imgdata/Aerial_Grey/s-gravenhage_33696704805_o.jpg");
  408. //	cv::Mat img = imread(str, CV_LOAD_IMAGE_GRAYSCALE);
  409. 	/*
  410. 	uint32 height, width, channel;
  411.  
  412. 	char fname[] = "C:/jwryu/RUG/2018/AlphaTree/imgdata/remote_sensing_img_8bit_8281x8185.raw";
  413. 	height = 8281;
  414. 	width = 8185;
  415. 	channel = 1;
  416. 	uint8 *img;
  417. 	FILE *fp;
  418.  
  419. 	img = (uint8*)malloc(height*width*sizeof(uint8));
  420. 	fopen_s(&fp, fname, "r");
  421. 	fread(img, sizeof(uint8), height*width*channel, fp);
  422. 	fclose(fp);
  423. 	memcpy(img, img1.data, height*width*channel*sizeof(uint8));
  424. 	*/
  425. 	//uint8 testimg[9] = { 4, 4, 1, 4, 2, 2, 1, 2, 0 };
  426.  
  427. 	//AlphaTree aTree;
  428. 	//	struct timeval stop, start;
  429. 	clock_t start, stop;
  430.  
  431. //	printf("Image size: %dx%dx%d", img.rows, img.cols, img.channels());
  432. 	//	gettimeofday(&start, NULL);
  433. 	start = clock();
  434. 	BuildAlphaTree(&tree, (uint8*)img.data, img.rows, img.cols, img.channels());
  435. //	BuildAlphaTree(&tree, (uint8*)img1.data, height, width, channel);
  436. 	stop = clock();
  437. 	//	gettimeofday(&stop, NULL);
  438. 	//		namedWindow("disp", WINDOW_AUTOSIZE); // Create a window for display.
  439. 		//	imshow("disp", img);                // Show our image inside it.
  440. 			//waitKey(0);
  441. 	printf("Time Elapsed: %f", (double)(stop - start) / 1000.0);
  442. 	getc(stdin);
  443. //	free(img);
  444. 	img.release();
  445. 	return 0;
  446. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:8:10: fatal error: opencv2/opencv.hpp: No such file or directory
 #include <opencv2/opencv.hpp>
          ^~~~~~~~~~~~~~~~~~~~
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/NxRen1
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!