[OpenCV] QuadTree Clustering C++ Code

2019.11.25

 

오늘은 QuadTree Clustering 알고리즘을 설명합니다. QuadTree 알고리즘은 상당히 많은 곳에서 사용되고 있습니다. QuadTree 알고리즘은 여러 장점이 있는데 그 중에서도 Clustering 하는데에 속도가 매우 빠르다는 장점이 유용한 경우가 많습니다. 구두로 간단히 QuadTree Clustering을 설명하자면, 알고리즘 이름에서 알다시피 네 개의 자식을 가지는 tree 구조로 되어있습니다. 이 것을 칼라 이미지에만 적용하여 설명하자면, 입력 이미지를 Root 노드로 하여 이미지를 네 등분하여 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 분할된 영역을 데이터로 가지는 자식을 생성합니다. 이미지의 생성된 자식 노드에 해당하는 영역의 화소값들의 평균을 구합니다. 그리고 해당 영역의 모든 픽셀들과 그 평균값과의 차이가 임계값보다 적으면 그 영역은 비슷한 색상을 가지고 있다고 판단하여 Clustering이 되며 그 영역의 평균값이 그 영역의 픽셀값이 됩니다. 그리고 임계값보다 크다면 다시 그 영역을 부모 노드로 하여 네 등분하는 영역을 자식 노드로 취하게 됩니다. 이렇게 반복을 진행하는데 분할된 영역의 넓이가 어느 임계값보다 작아지기전까지 분할을 하게 됩니다. 이렇게 되면 전체 알고리즘에 필요한 하이퍼 파라미터는 두 개입니다. 픽셀들과 평균값의 차이를 결정짓는 임계값1과 영역의 쪼개지는 넓이의 최소점을 의미하는 임계값2 입니다. 앞서 포스팅한 K-means Clustering과 비교해보면 분할하는 사각형의 넓이를 충분히 작게하면 훨씬 더 보기 좋은 결과 이미지를 내보내게 되고 비교도 안될정도로 빠른 속도로 Clustering을 진행합니다. 두 알고리즘의 차이는 Global하다는 것과 Local하다는 것의 차이가 있습니다. 아래는 C++로 구현된 QuadTree Code 입니다.

 

main.cpp

#include <iostream>
#include <vector>
#include <ctime>

#include "QuadTree.h"
#include "opencv342.h"

using namespace std;

cv::Mat QuadTree_Cluster(cv::Mat, int minArea, float threshold);

int main()
{
	// Input Image의 파일명
	string CLUSTER[5] = { "12003.jpg", "25098.jpg", "97017.jpg", "151087.jpg", "181018.jpg" };
	string path = "testImage/";

	// QuadTree Clustering
	for (int i = 0; i < 5; i++) {
		cv::Mat img = cv::imread(path + CLUSTER[i]);
		cv::Mat result;
		int minArea = 10;
		float threshold = 5.0;

		result = QuadTree_Cluster(img, minArea, threshold); // src, minArea, threshold
		cv::imwrite(path + "Result_Quad/" + CLUSTER[i], result);
	}


	return 0;
}

cv::Mat QuadTree_Cluster(cv::Mat src, int minArea, float threshold) {
	cv::Mat result;

	QuadTree clustering(src, minArea, threshold);

	result = clustering.getResultMat();

	return result;
}

 

QuadTree.h

#pragma once
#include <iostream>

#include "opencv342.h"

using namespace std;

class QuadTree
{
public:
	QuadTree(cv::Mat src, int area, float threshold);
	~QuadTree();

	cv::Mat getResultMat();
	
private:
	cv::Mat img;
	cv::Mat dst;

	uchar* sImage;
	uchar* dImage;
	int minArea;
	float thr;

	struct Node {
		int x, y, width, height;
		Node* Children;
	};

	Node root;

private:
	cv::Point3f average(int x, int y, int width, int height);
	float measureDetail(int x, int y, int width, int height);
	void createQuadTree(Node node);
	void divideNode(Node& node);
	void coloring(cv::Point3f avg, int x, int y, int width, int height);
	void TestShowImage(int x, int y, int width, int height);
};

QuadTree.cpp

#include "QuadTree.h"

QuadTree::QuadTree(cv::Mat src, int area, float threshold)
	:img(src), minArea(area), thr(threshold)
{
	dst = cv::Mat::zeros(img.size(), CV_8UC3);

	sImage = img.data;
	dImage = dst.data;

	root.x = 0;
	root.y = 0;
	root.width = img.cols;
	root.height = img.rows;

	createQuadTree(root);

	//cv::imshow("Test from QuadTree", img);
	//cv::waitKey(0);
}

QuadTree::~QuadTree() {
	delete root.Children;
}

/* Calculates the average color of a rectangular region of a grid */
cv::Point3f QuadTree::average(int x, int y, int width, int height) {	
	int redSum = 0;
	int greenSum = 0;
	int blueSum = 0;

	// Adds the color values for each channel.
	for (int r = y; r < y + height; r++) {
		for (int c = x; c < x + width; c++) {
			int offset = r * img.cols * 3 + c * 3;
			
			uchar B = sImage[offset + 0]; //img.at<cv::Vec3b>(r, c)[0];
			uchar G = sImage[offset + 1]; //img.at<cv::Vec3b>(r, c)[1];
			uchar R = sImage[offset + 2]; //img.at<cv::Vec3b>(r, c)[2];

			blueSum += B;
			greenSum += G;
			redSum += R;
		}
	}

	// number of pixels evaluated
	int area = width * height;
	return cv::Point3f(blueSum / area, greenSum / area, redSum / area);
}

/* Measures the amount of detail of a rectangular region of a grid */
float QuadTree::measureDetail(int x, int y, int width, int height) {
	cv::Point3f averageColor = average(x, y, width, height);
	
	int blue = averageColor.x;
	int red = averageColor.z;
	int green = averageColor.y;	
	int colorSum = 0;

	// Calculate the distance between every pixel in the region
	// and the average color. The Manhattan distance is used, and
	// all the distances are added.
	for (int r = y; r < y + height; r++) {
		for (int c = x; c < x + width; c++) {
			int offset = r * img.cols * 3 + c * 3;

			uchar B = sImage[offset + 0];
			uchar G = sImage[offset + 1];
			uchar R = sImage[offset + 2];

			colorSum += abs(blue - B);
			colorSum += abs(green - G);
			colorSum += abs(red - R);
		}
	}
	// Calculates the average distance, and returns the result.
	// We divide by three, because we are averaging over 3 channels.
	int area = width * height;
	return colorSum / (3 * area);
}

void QuadTree::createQuadTree(Node node) {
	if (measureDetail(node.x, node.y, node.width, node.height) < thr || node.width * node.height <= minArea) {
		cv::Point3i avgBGR = average(node.x, node.y, node.width, node.height);
		coloring(avgBGR, node.x, node.y, node.width, node.height);
	}
	else {
		//TestShowImage(node.x, node.y, node.width, node.height);
		divideNode(node);
		createQuadTree(node.Children[0]);
		createQuadTree(node.Children[1]);
		createQuadTree(node.Children[2]);
		createQuadTree(node.Children[3]);
	}
}

void QuadTree::divideNode(Node& node) {
	// Node division
	node.Children = new Node[4];

	int x = node.x;
	int y = node.y;
	int width = node.width;
	int height = node.height;

	node.Children[0].x = x;
	node.Children[0].y = y;
	node.Children[0].width = width / 2;
	node.Children[0].height = height / 2;

	node.Children[1].x = x + width / 2;
	node.Children[1].y = y;
	node.Children[1].width = width - width / 2;
	node.Children[1].height = height / 2;

	node.Children[2].x = x;
	node.Children[2].y = y + height / 2;
	node.Children[2].width = width / 2;
	node.Children[2].height = height - height / 2;
	
	node.Children[3].x = x + width / 2;
	node.Children[3].y = y + height / 2;
	node.Children[3].width = width - width / 2;
	node.Children[3].height = height - height / 2;
}

// Coloring average bgr value in destination image.
void QuadTree::coloring(cv::Point3f avg, int x, int y, int width, int height) {
	uchar* dImage = dst.data;
	for (int r = y; r < y + height; r++) {
		for (int c = x; c < x + width; c++) {
			int offset = r * img.cols * 3 + c * 3;
			dImage[offset + 0] = avg.x;
			dImage[offset + 1] = avg.y;
			dImage[offset + 2] = avg.z;
		}
	}
}

void QuadTree::TestShowImage(int x, int y, int width, int height) {
	cv::imshow("Test", img(cv::Rect(x, y, width, height)));
	cv::waitKey(0);
}
cv::Mat QuadTree::getResultMat() {
	return dst;
}