POPCNTによるハミング距離計算とステレオ対応への応用 名古屋工業大学 福嶋慶繁 Twitter: @fukushima1981
POPCNT• POPCNT: – データの非ゼロのビット数を数える – Population countの略• VC,GCCでは下記関数で,値が確保可能 – Int val = _mm_popcnt_u32(unsigned long)...
なんの役に立つの?ハミング距離が計算可能
ハミング距離(Hamming Distance)• データ中のビットの違いの数• 例 AとBのハミング距離は? – A:00100101 – B:00101011 – 3つ異なるので3 – L0ノルムに似た距離尺度
popcnt使い方• popcnt: – ビット中の非ゼロの数を高速に数えてくれる• ハミング距離: – 2つのビット列のうち異なるビットの数• つまり,2つのビット列の異なり具合を表すビット列をpopcntすれば即座 にハミング距離...
POPCNTによるハミング距離• 入力データ – A:00100101 – B:00101011• 排他的論理和 – A^B:00001110• POPCNT – popcnt(00001110)=3• AとBのハミング距離は3!
例題:ステレオマッチング• ステレオマッチング – 左右の画素の一致度を図り,最も一致した画素 を元に奥行きを計算する – 単純な距離尺度:絶対誤差,二乗誤差 • abs(L-R):SAD • (L-R)^2 :SSD – ハミング距離...
CENSUS Transform (1/2)• 画素中に適当なウィンドウを張り,中心の画素と周 辺の画素との大小関係をバイナリベクトルに変換す る変換• 中心<周辺 ? 1 : 0• ベクトル長はウィンドウの大きさに依存
CENSUS Transform (2/2)• 8bitのCENSUS変換(つまり窓の面積が,中心を除く8画素)な ら画像として表現も可能• それ以上の窓サイズになると桁があふれて画像としては可 視化不可能 入力画像 ...
CENSUS変換によるステレオマッチング1. 左右の画像(Iml,Imr)をCENSUS変換した画像を作成: (Iml,Imr)→(Imlcensus,Imrcensus )2. 右の変換画像をある視差dだけシフト Imrcensu...
例題:ステレオマッチング(入力) Left Image Right Image 左右ともども9x1の窓で全体をCENSUS変換
例題:ステレオマッチング(出力) SAD: CENSUS: 95 msec 107 msecSADという非常に簡単な絶対値差分と比べて速度面はほとんど変わらない
CENSUS変換の利点• 輝度値を直接比較しないので照明変動につ よい – 中央との相対関係をもとに比較• ノイズに強い – バイナリの値を比較するので,微小なノイズの影 響が少ない• 模様が少ない領域での対応付けが安定する – 中心との...
Sample code Stereo Matching のサンプルコード:詳細は次ページvoid calcHammingDistance8u(Mat& src1, Mat& ...
ハミング距離サンプル 画像Aと画像Bの各画素のハミング距離計測のサンプル(OpenCVによる実装)void calcHammingDistance8u(Mat& src1, Mat& src2, Mat& dest){ if...
画像のCENSUS変換サンプル9x1の横長の窓でのCENSUS変換.条件を満たしたら1とのbit orを取って,次に備えてbit shiftしているだけ void censusTrans8u_8x1(Mat& src, Mat& dest) {...
of 16

Popcntによるハミング距離計算

SSE4.2に採用されているpopcnt命令を使ってハミング距離を計算する方法の解説.例題としてCENSUS変換によるステレオ対応づけを説明しています.
Published on: Mar 4, 2016
Published in: Technology      
Source: www.slideshare.net


Transcripts - Popcntによるハミング距離計算

  • 1. POPCNTによるハミング距離計算とステレオ対応への応用 名古屋工業大学 福嶋慶繁 Twitter: @fukushima1981
  • 2. POPCNT• POPCNT: – データの非ゼロのビット数を数える – Population countの略• VC,GCCでは下記関数で,値が確保可能 – Int val = _mm_popcnt_u32(unsigned long)• SSE4.2から対応 – 一昔前のCore i7よりも新しいCPUのみ対応
  • 3. なんの役に立つの?ハミング距離が計算可能
  • 4. ハミング距離(Hamming Distance)• データ中のビットの違いの数• 例 AとBのハミング距離は? – A:00100101 – B:00101011 – 3つ異なるので3 – L0ノルムに似た距離尺度
  • 5. popcnt使い方• popcnt: – ビット中の非ゼロの数を高速に数えてくれる• ハミング距離: – 2つのビット列のうち異なるビットの数• つまり,2つのビット列の異なり具合を表すビット列をpopcntすれば即座 にハミング距離が求まる. – それはAとBの排他的論理和で表現可能 – 2つの値が同じなら0違うなら1を出力する論理演算 – A XOR B, c,c++では, A^B; popcnt(A^B);これだけでハミング距離が測定できる!
  • 6. POPCNTによるハミング距離• 入力データ – A:00100101 – B:00101011• 排他的論理和 – A^B:00001110• POPCNT – popcnt(00001110)=3• AとBのハミング距離は3!
  • 7. 例題:ステレオマッチング• ステレオマッチング – 左右の画素の一致度を図り,最も一致した画素 を元に奥行きを計算する – 単純な距離尺度:絶対誤差,二乗誤差 • abs(L-R):SAD • (L-R)^2 :SSD – ハミング距離を使う距離尺度もある • CENSUS変換
  • 8. CENSUS Transform (1/2)• 画素中に適当なウィンドウを張り,中心の画素と周 辺の画素との大小関係をバイナリベクトルに変換す る変換• 中心<周辺 ? 1 : 0• ベクトル長はウィンドウの大きさに依存
  • 9. CENSUS Transform (2/2)• 8bitのCENSUS変換(つまり窓の面積が,中心を除く8画素)な ら画像として表現も可能• それ以上の窓サイズになると桁があふれて画像としては可 視化不可能 入力画像 CENSUS変換画像
  • 10. CENSUS変換によるステレオマッチング1. 左右の画像(Iml,Imr)をCENSUS変換した画像を作成: (Iml,Imr)→(Imlcensus,Imrcensus )2. 右の変換画像をある視差dだけシフト Imrcensus (x)→ Imrcensus (x-d)3. シフトした右CENSUS画像と左CENSUS画像のハミング 距離を計算 distance(d)= Hamming(Imlcensus (x) , Imrcensus (x-d))4. もっともハミング距離が小さかった視差値をその画素 の視差として採用 disp = argmind distance(d)
  • 11. 例題:ステレオマッチング(入力) Left Image Right Image 左右ともども9x1の窓で全体をCENSUS変換
  • 12. 例題:ステレオマッチング(出力) SAD: CENSUS: 95 msec 107 msecSADという非常に簡単な絶対値差分と比べて速度面はほとんど変わらない
  • 13. CENSUS変換の利点• 輝度値を直接比較しないので照明変動につ よい – 中央との相対関係をもとに比較• ノイズに強い – バイナリの値を比較するので,微小なノイズの影 響が少ない• 模様が少ない領域での対応付けが安定する – 中心との差分→微分のような効果があるためエッ ジ(模様)を強調する効果
  • 14. Sample code Stereo Matching のサンプルコード:詳細は次ページvoid calcHammingDistance8u(Mat& src1, Mat& src2, Mat& dest){ if(dest.empty())dest.create(src1.size(),CV_8U); int i,j; uchar* s1 = src1.ptr<uchar>(0); uchar* s2 = src2.ptr<uchar>(0); uchar* d = dest.ptr<uchar>(0); int count=0; const int hstep = src1.cols/16; const int rad= src1.cols- hstep*16; for(j=src1.rows;j--;) { //base for(i=src1.cols;i--;) { *d = _mm_popcnt_u32((unsigned int)(*s1^*s2)); s1++;s2++,d++; } }}void censusTrans8u_8x1(Mat& src, Mat& dest){ if(dest.empty())dest.create(src.size(),CV_8U); const int r=4; const int r2=2*r; Mat im;copyMakeBorder(src,im,0,0,r,r,cv::BORDER_REPLICATE); int i,j,n; uchar* s = im.ptr<uchar>(0);s+=r; uchar* d = dest.ptr<uchar>(0); for(j=0;j<src.rows;j++) { for(i=0;i<src.cols;i++) { uchar val = 0;//init value uchar* ss=s-r; for(n = 0;n<r;n++) { //if (*ss<*s)val|=1; val = (*ss<*s) ? val|1 : val; ss++; val <<=1; } ss++;//skip r=0 for(n = 0;n<r;n++) { val = (*ss<*s) ? val|1 : val; ss++; val <<=1; } *d=val; d++; s++; } s+=r2; }}void shiftImage8u(Mat& src, Mat& dest, const int shift){ if(dest.empty())dest.create(src.size(),CV_8U); if(shift>=0) { const int step = src.cols; uchar* s = src.ptr<uchar>(0); uchar* d = dest.ptr<uchar>(0); int j;j=0; for(;j<src.rows;j++) { const uchar v = s[0]; memset(d,v,shift); memcpy(d+shift,s,step-shift); s+=step;d+=step; } } else { const int step = src.cols; uchar* s = src.ptr<uchar>(0); uchar* d = dest.ptr<uchar>(0); int j;j=0; for(;j<src.rows;j++) { const uchar v = s[step-1]; memcpy(d,s+shift,step-shift); memset(d+step-shift,v,shift); s+=step;d+=step; } }}void stereoCensus8x1(Mat& leftim, Mat& rightim, Mat& dest, int minDisparity, int range, int r){ if(dest.empty())dest.create(leftim.size(),CV_8U); Mat lim,rim; if(leftim.channels()==3)cvtColor(leftim,lim,CV_BGR2GRAY); else lim=leftim; if(rightim.channels()==3)cvtColor(rightim,rim,CV_BGR2GRAY); else rim=rightim; Mat limCensus,rimCensus; censusTrans8u_8x1(lim,limCensus); censusTrans8u_8x1(rim,rimCensus); Mat rwarp; Mat distance; vector<Mat> dsv(range); for(int i=0;i<range;i++) { shiftImage8u(rimCensus , rwarp,minDisparity+i); calcHammingDistance8u(limCensus,rwarp,distance); blur(distance,dsv[i],Size(2*r+1,2*r+1)); } Size size = dest.size(); Mat cost = Mat::ones(size,VOLUME_TYPE)*255; Mat mask; const int imsize = size.area(); for(int i=0;i<range;i++) { Mat pcost; cost.copyTo(pcost); min(pcost,dsv[i],cost); compare(pcost,cost,mask,cv::CMP_NE); dest.setTo(i+minDisparity,mask); }} void stereoSAD(Mat& leftim, Mat& rightim, Mat& dest, int minDisparity, int range, int r){ if(dest.empty())dest.create(leftim.size(),CV_8U); Mat lim,rim; if(leftim.channels()==3)cvtColor(leftim,lim,CV_BGR2GRAY); else lim=leftim; if(rightim.channels()==3)cvtColor(rightim,rim,CV_BGR2GRAY); else rim=rightim; Mat rwarp; Mat distance; vector<Mat> dsv(range); for(int i=0;i<range;i++) { shiftImage8u(rim , rwarp,minDisparity+i); absdiff(lim,rwarp,distance); blur(distance,dsv[i],Size(2*r+1,2*r+1)); } Size size = dest.size(); Mat cost = Mat::ones(size,VOLUME_TYPE)*255; Mat mask; const int imsize = size.area(); for(int i=0;i<range;i++) { Mat pcost; cost.copyTo(pcost); min(pcost,dsv[i],cost); compare(pcost,cost,mask,cv::CMP_NE); dest.setTo(i+minDisparity,mask); }}
  • 15. ハミング距離サンプル 画像Aと画像Bの各画素のハミング距離計測のサンプル(OpenCVによる実装)void calcHammingDistance8u(Mat& src1, Mat& src2, Mat& dest){ if(dest.empty())dest.create(src1.size(),CV_8U); int i,j; uchar* s1 = src1.ptr<uchar>(0); uchar* s2 = src2.ptr<uchar>(0); uchar* d = dest.ptr<uchar>(0); for(j=src1.rows;j--;) { for(i=src1.cols;i--;) { *d = _mm_popcnt_u32((unsigned int)(*s1^*s2)); s1++;s2++,d++; } }}
  • 16. 画像のCENSUS変換サンプル9x1の横長の窓でのCENSUS変換.条件を満たしたら1とのbit orを取って,次に備えてbit shiftしているだけ void censusTrans8u_8x1(Mat& src, Mat& dest) { if(dest.empty())dest.create(src.size(),CV_8U); const int r=4; const int r2=2*r; Mat im;copyMakeBorder(src,im,0,0,r,r,cv::BORDER_REPLICATE); int i,j,n; uchar* s = im.ptr<uchar>(0);s+=r; uchar* d = dest.ptr<uchar>(0); for(j=0;j<src.rows;j++) { for(i=0;i<src.cols;i++) { uchar val = 0;//init value uchar* ss=s-r; for(n = 0;n<r;n++) { val = (*ss<*s) ? val|1 : val; ss++; val <<=1; } ss++;//skip r=0 for(n = 0;n<r;n++) { val = (*ss<*s) ? val|1 : val; ss++; val <<=1; } *d=val; d++; s++; } s+=r2; } }

Related Documents