Qt/Gcc
2014.2.11作成
Appendex
A ソート(sort)と単一化(unique)
画像データは大きなデータですので、色などを扱う場合に単一化をしたい場合があります。
たとえば、ある領域で色を計算したいとき、画像は近い画像同士や領域同士で相関が
あることが多いです。つまり、R、G、Bの値は隣り合った画像同士、同じ値になる場合があります。
このとき、単一化することで計算を少なくすることができます。
たとえば、以下のようなR、G、Bの値を持った10個のデータがあったとします。
data
0:Red
193,Green 208,Blue 14
1:Red 82,Green 180,Blue 253
2:Red 121,Green 114,Blue
120
3:Red 128,Green 64,Blue 165
4:Red 128,Green 64,Blue 165
5:Red
82,Green 180,Blue 253
6:Red 255,Green 128,Blue 64
7:Red 82,Green 180,Blue
253
8:Red 82,Green 180,Blue 253
9:Red 82,Green 180,Blue
253
これを、単一化すると以下のようになります。
unique result
0:Red 255,Green 128,Blue
64
1:Red 193,Green 208,Blue 14
2:Red 128,Green 64,Blue 165
3:Red
121,Green 114,Blue 120
4:Red 82,Green 180,Blue
253
これをみていただいてわかると思いますが、ソートされています。
単一化の前にソートをします。
つまり順番としては、
data->sort->unique(result)となります。
くどいですが、以下にデータを示します。
data
0:Red
193,Green 208,Blue 14
1:Red 82,Green 180,Blue 253
2:Red 121,Green 114,Blue
120
3:Red 128,Green 64,Blue 165
4:Red 128,Green 64,Blue 165
5:Red
82,Green 180,Blue 253
6:Red 255,Green 128,Blue 64
7:Red 82,Green 180,Blue
253
8:Red 82,Green 180,Blue 253
9:Red 82,Green 180,Blue 253
sort
data
0:Red 255,Green 128,Blue 64
1:Red 193,Green 208,Blue 14
2:Red
128,Green 64,Blue 165
3:Red 128,Green 64,Blue 165
4:Red 121,Green 114,Blue
120
5:Red 82,Green 180,Blue 253
6:Red 82,Green 180,Blue 253
7:Red
82,Green 180,Blue 253
8:Red 82,Green 180,Blue 253
9:Red 82,Green 180,Blue
253
unique result
0:Red 255,Green 128,Blue 64
1:Red 193,Green 208,Blue
14
2:Red 128,Green 64,Blue 165
3:Red 121,Green 114,Blue 120
4:Red
82,Green 180,Blue 253
以下プログラムを説明していきます。
このプログラムはC++のSTLのstd::sortとstd::uniqueを使います。
このために、以下2つのライブラリをインクルードします。
#include
<cstdlib>
#include
<algorithm>
sortとuniqueはvectorデータに対して実施します。そこで、以下のライブラリもインクルードします。
#include
<vector>
●CSortUnqRgbクラス
ソートと単一化の処理はCSortUnqRgbクラスで処理します。
RGB画素のデータをベクタデータとして扱うため、構造体を定義して構造体を
ベクタデータとします。構造体の配列と同じ考え方です。
struct SoRGB{
int
Red;
int
Green;
int
Blue;
};
vector<SoRGB>
sorgb;//構造体をベクタデータとする。
sortもuniqueもプレディケート(predicate判断基準、断定)を第３引数に指定できます。
sortするときは、Redを第一優先、Greenを第二優先、Blueを第三優先として並び替えをしたいため
プレディケートを定義します。その関数が以下の二つです。
static bool CompRGB(const SoRGB& rLeft,const SoRGB&
rRight);//sortプレディケート
static bool UnqRGB(const SoRGB& rLeft,const
SoRGB&
rRight);//uniqueプレディケート
単一化はこの関数の中で実施します。
void
MakeUniqu(vector<SoRGB>&
rgb);//単一化関数ここでUniqueにする。
以下はテストデータと結果の表示用関数です。
void
DispData(vector<SoRGB> vecrgb);//結果表示用関数
void
MakeData_unqtes(vector<SoRGB>& vecrgb,int
nNumOf);//テストデータ作成用関数
以下プログラムです。
#include <cstdlib>
#include <algorithm>
#include
<vector>
#include <time.h>
#include<iostream>
using
namespace std;
class CSortUnqRgb {
public:
struct SoRGB{
int
Red;
int
Green;
int
Blue;
};
vector<SoRGB> sorgb;//構造体をベクタデータとする。
static bool
CompRGB(const SoRGB& rLeft,const SoRGB&
rRight);//プレディケート
static bool UnqRGB(const SoRGB&
rLeft,const SoRGB& rRight);//プレディケート
void
DispData(vector<SoRGB> vecrgb);//結果表示用関数
void
MakeUniqu(vector<SoRGB>&
rgb);//単一化関数ここでUniqueにする。
void MakeData_unqtes(vector<SoRGB>& vecrgb,int
nNumOf);//テストデータ作成用関数
};
bool
CSortUnqRgb::UnqRGB(const SoRGB& rLeft,const SoRGB&
rRight)
{
int
nDiff; //
両要素の差
nDiff=rLeft.Red -
rRight.Red;
if(nDiff
!=0)
return
false;
nDiff = rLeft.Green -
rRight.Green;
if(nDiff
!=0)
return
false;
nDiff = rLeft.Blue -
rRight.Blue;
if(nDiff
!=0)
return
false;
return
true;//3つの要素がすべて同じならtrueを返す。同じ組があるとして削除する。
//以下メモ
/*nDiff = rLeft.Red - rRight.Red;
if(nDiff ==
0){
nDiff = rLeft.Green -
rRight.Green;
if(nDiff
==0){
nDiff = rLeft.Blue -
rRight.Blue;
if(nDiff ==0)
return
true;
}
}*/
//return
false;//trueにすると同じデータのみを抽出
}
bool CSortUnqRgb::CompRGB(const SoRGB&
rLeft,const SoRGB&
rRight)
{
int
nDiff; //
両要素の差
nDiff = rLeft.Red - rRight.Red;
if(nDiff != 0){
if(nDiff <
0)
return
false;
if(nDiff >
0)
return
true;
}
nDiff = rLeft.Green -
rRight.Green;
if(nDiff !=
0){
if(nDiff <
0)
return
false;
if(nDiff >
0)
return
true;
}
nDiff
= rLeft.Blue - rRight.Blue;
if(nDiff !=
0){
if(nDiff <
0)
return
false;
if(nDiff >
0)
return
true;
}
return
false;//データ全部同じだった場合はfalseを返す決まり
}
void
CSortUnqRgb::MakeUniqu(vector<SoRGB>& rgb)
{
int
i;
i=0;
vector<SoRGB>::iterator it;
it=std::unique
(rgb.begin(), rgb.end(),UnqRGB); // 10 20 30 20 10 ? ?
?
?
//
^
rgb.resize( std::distance(rgb.begin(),it) ); // 10 20 30 20 10
}
void
CSortUnqRgb::MakeData_unqtes(vector<SoRGB>& vecrgb,int
nNumOf)
{
int i;
const int sum =
3;
struct SoRGB chw;
chw.Red=193;
chw.Green=208;
chw.Blue=14;
vecrgb.push_back(chw);
chw.Red=82;
chw.Green=180;
chw.Blue=253;
vecrgb.push_back(chw);
chw.Red=121;
chw.Green=114;
chw.Blue=120;
vecrgb.push_back(chw);
chw.Red=128;
chw.Green=64;
chw.Blue=165;
vecrgb.push_back(chw);
chw.Red=128;
chw.Green=64;
chw.Blue=165;
vecrgb.push_back(chw);
chw.Red=82;
chw.Green=180;
chw.Blue=253;
vecrgb.push_back(chw);
chw.Red=255;
chw.Green=128;
chw.Blue=64;
vecrgb.push_back(chw);
for(i = 0; i < sum; i++)
{
chw.Red=82;
chw.Green=180;
chw.Blue=253;
vecrgb.push_back(chw);
}
}
void CSortUnqRgb::DispData(vector<SoRGB>
vecrgb)
{
int i;
i=0;
vector<SoRGB>::iterator l=vecrgb.begin();
while(l!=vecrgb.end()){
cout << i << ":"
<< "Red " << l->Red <<
",";
cout << "Green "
<< l->Green << ",";
cout << "Blue " <<
l->Blue << endl;
l++;
i++;
}
}
/*
*
*/
int main(int argc,
char** argv) {
CSortUnqRgb
SR;
SR.MakeData_unqtes(SR.sorgb,10);
cout << "data" <<
endl;
SR.DispData(SR.sorgb);//test
sort(SR.sorgb.begin(),SR.sorgb.end(),SR.CompRGB);
cout << "sort data" <<
endl;
SR.DispData(SR.sorgb);//test
SR.MakeUniqu(SR.sorgb);
cout
<< "unique result" <<
endl;
SR.DispData(SR.sorgb);//result
cout <<
"END Process";
return 0;
}