二維變換演算法

⑴ Radon變換及逆變換公式的來歷及證明過程，要詳細的，不懂得不要回答

radon變換 兩維情況下radon變換大致可以這樣理解：一個平面內沿不同的直線（直線與原點的距離為d，方向角為alfa）對f（x，y）做線積分，得到的像F(d,alfa)就是函數f的Radon變換。也就是說，平面（d，alfa）的每個點的像函數值對應了原始函數的某個線積分值。一個更直觀的理解是，假設你的手指被一個很強的平行光源透射，你迎著光源看到的手指圖像就是手指的光衰減系塌塵數的三維Radon變換（小小的推廣）在給定方向（兩個角坐標）的時候的值， 一個最簡單而直接的應用就是拿來檢測圖像裡面含有的直線成分，很顯然地，任何直線都會導致Randon像在該直線對應（d，alfa）處的極值。 具體的CT斷層團逗禪影像重建演算法當中其實沒怎麼用到Radon變換，或者說Radon變換僅僅只有一點點理論上的意義。原因是：CT機做掃描：球管發出X-ray，經過人體，被吸收一部分，進入檢測器隊列（球管是旋轉的，檢測器呈扇形分布，很老的和很新的除外，老式的ct做平行掃描，效率低，很新式的什麼多層螺旋掃描，我也不知道咋回事）顯然檢測器讀數就是人體的x-ray吸收系數（是空間的函數）對相應路徑的線積分，所以這樣轉一圈下來再把所有的檢測器讀數值按照（d，alfa）的方式排列一下就算完成了某個被檢測截面的Radon變換了，這個過程是人體和X-rayscaner一起完成的，顯然不幹軟體什麼事。接下來，照理說是要靠計算機把獲得的數據做一個逆Radon變換，就能得到被檢測截面的X-ray吸收系數的分布圖像了。CT的圖像其實就是一個吸收系數的圖，類似的B超或者聲納之類的圖像是大致是一個彈性模量的圖（反射聲波）... 但是接下來這里有一個問題就是Radon變換是不是可逆，google了下好像是可逆的，我的理解： 1）有另外一種求逆方法，就是解代數方程，簡化地說可以大致設想把整個截面離散網格化，每個格子對應一個吸收系數，把每根掃描積分路徑經過的格子按照權重（顯然透心涼和擦點皮對吸收的貢獻不同）作累加，令他們等於相應Radon值（積分變成了加權累加而已）顯然設計好的話，這個方程組肯定是有解的（不過運算量會很龐大，比如一個512X512的網格...） 2）工程師不問這么無聊不切實際的問題，所以以前學的時候就壓根沒想到。 3）最重要的原因，是下面要說的求逆問題，竟然變成了二維的fourier逆變換。所以忘掉Radon變換吧。 有這樣一個事實：把某個角度坐標alfa對應的一「條」Radon值（一系列檢測器的讀數，也實際上就是原始截面吸收系數在方向為alfa+-Pi/2直線簇上的線積分值）作一個fourier變換，得到的就是整個原始被檢測截面（吸收系數）的二維fourier像在某條直線上的值（這條直線經過頻域的原點並且方向為alfa）如果把所有角度的Radon值作一維Fourier變換，然後按照合適的角度（alfa）經過原點把這些一維fourier像值放在頻域平面上，就得到了整個二維fourier像！！！這個其實直觀上很容易想像其合理性，還是以手指頭為例（不考慮它指向的方向）對著光源看，從左至右，透光率不同產生明暗的變化，亮暗本身是沿前後方向的積分結果決定，但是相鄰的亮暗變化卻反應了整個手指截面的從左至右這個方向上的頻域信息，看到的細節越多，頻域的高頻分量越多（與前後方向的細節毫無關系，因為被radon積分掉了）。 以上關於CT其實是過分簡化的描述，只能提供一個大致的原理。實際情況會有些不同，首先檢測器讀數是有限空間的，這就是相當於理想的投影函數乘了一個窗函數（某段區間內為一，其他地方為零的函數），在頻域內窗函數會「擴散」所以他們頻域做卷積的結果是頻域的擴展。也可以說成是，對於非周期函數（包括周期不為無窮大）的fourier級數在邊界的間斷處只能是平均收斂，「平均」的結果就是在光滑的地方擬合的很好，在間斷點處發生振盪。工程中管這個叫做吉布斯（Gibbs）效應，它告訴我們：用有限項指消級數的和去表示一個函數，隨著項數的增加，振盪發生的位置會越來越接近間斷點，但是它的擺幅不變（寫到這忽然覺得它的名字似乎翻譯成「擠不死」更貼切）另外，檢測器只能讀出空間上分立的數值，所謂的取樣過程就是投影函數乘一個迪拉克函數組成的序列（假設周期為L）而迪拉克序列變換到頻域仍然是一個迪拉克序列，只是周期變成了1/L。投影和取樣序列相乘在頻域就是卷積，出來的結果就是具有了周期頻譜，顯然可用的只能是原點（DC）所在的一個周期內的數據。當L越來越小的時候，頻譜周期越來越大，空間解析度越來越高。當L為有限的時候，解析度如果用頻率來表示的話，從原點（「直流」分量）開始算，由於周期性緣故顯然最高到1/2L處。 設想一間黑屋子，唯一的光源是一個可調節頻率的頻閃光源，一台電風扇。假定光源閃爍頻率為w，顯然理論上能夠檢測到的風扇轉速u將允許加上任意整數個w。比方說，每秒亮一下，你看到了風扇轉動了1/4圈，那麼你可以認為風扇每秒轉動1/4圈，但也可以是5/4圈（多轉了一圈，有何不可？），9/4圈...也可以是(反著轉)-3/4圈，-7/4圈...原因就是前面說的，用一個脈沖序列（光源頻閃）去做取樣，必然會得到周期性的頻譜。接下來，當光源的閃爍頻率和風扇的轉速（用轉/秒來表述）相等的時候，你將看到風扇是停止的，當光源頻率高於風扇轉速的兩倍時，你才能看到風扇正常的轉動，如果光源頻率介於風扇轉速一倍和兩倍之間，那你會看到風扇倒著轉了。這里的情況被稱為頻譜混疊。此類現象生活中常遇到。另外，函數變換本身還帶來了坐標平移一類的問題。實際當中用的最多的是一種叫做濾波反投影的演算法來實現斷層重建，說穿了關鍵就針對以上一些問題設計合理的濾波器。 另外值得一提的是，這里用到的數學大概一百年前就有了，但是隨著計算機技術的進步，具體實現的時候，出現過不同的版本。譬如說，70年代的商業運行的CT（256X256），帶一台長得像電冰箱般的「卷積器（convolver）」，顧名思義，它的濾波器實現大概是用DSP做卷積的（離散的卷積就是一系列的移位連乘連加）。而現代，隨著硬體技能的突飛猛進，FFT不成問題了，這個交給CPU在頻域內作乘法就能搞定。退一步說，我甚至懷疑，那個形體巨大的Convolver做卷積的性能恐怕未必能趕上我正在碼字的電腦。此刻，它正在運行音樂播放軟體foorbar，同時一起運行的還有一堆插件（也可看作卷積器），比如老式電子管音色，教堂混響，耳機模擬現場音效之類的... 以上這些基本上是相關領域的abc，沒有深入，基本憑借記憶，說法可能和專門的教材不完全一樣，而且很多地方一知半解，肯定會有謬誤，大家隨便看看不可當真，當然歡迎拍磚。

⑵ 圖像演算法中的二維傅立葉變換(DCT)及蝶形演算法(butterfly algorithm)

本文討論圖像演算法中的核心概念，即二維傅立葉變換(DCT)與蝶形演算法(butterfly algorithm)。首先，我們概述了離散2維Fourier的基礎知識，雖然這里不進行深入講解，但有需要時可參考fourier.eng.hmc.e/e10...的資料。

在圖像處理和壓縮中，如JPEG等，傅立葉變換發揮著關鍵作用。我們通常不會對整個圖像進行傅立葉變換，而是將其分割成小塊，如4x4或8x8像素塊，以達到計算效率與質量平衡的目的。

接下來，以4x4像素塊為例，解析DCT變換及蝶形演算法的原理。首先，我們定義了4x4矩陣的DCT變換矩陣。通過推導，我們發現變換矩陣為[公式]。在實際應用中，文獻通常採用簡化形式，其矩陣為[公式]，其中系數C影響直流系數的大小，對圖像亮度處理尤為重要。盡管C的引入改變了變換矩陣的形式，但它不會對圖像處理結果造成實質性的影響。

基於此，我們直接使用簡化後的DCT變換矩陣，即[公式]，進行圖像變換。隨後，我們引入蝶形演算法，通過合並重復的計算組合，大大降低運算量。以4x4矩陣為例，蝶形演算法圖示展示了如何合並計算路徑，形成依賴關系，從而減少重復計算，提高計算效率。

總結，二維傅立葉變換(DCT)與蝶形演算法(butterfly algorithm)在圖像演算法中扮演關鍵角色，通過分割圖像、變換矩陣的簡化以及蝶形演算法的應用，實現高效且精確的圖像處理與壓縮。

⑶ 如何用findhomography計算二維仿射變換矩陣

1.計算方法不同：通過跟蹤源碼，發現getPerspectiveTransform用的是SVD分解，findHomography看不出是用什麼方法（沒注釋棗迅，一堆等式）。但兩者計算結果是一樣的。
2.輸入參數不同：getPerspectiveTransform只會拿前4個點去計算，findHomography則會拿一堆點(>=4)去計算(其是不斷從一堆點中重復拿出4個點去計算出一個結果，再採用一些優化演算法凳搏此RANSAC/銀神LMEDS去篩選出最優解)。

⑷ 怎樣用C語言實現FFT演算法啊

1、二維FFT相當於對行和列分別進行一維FFT運算。具體的實現辦法如下：
先對各行逐一進行一維FFT，然後再對變換後的新矩陣的各列逐一進行一維FFT。相應的偽代碼如下所示：
for (int i=0; i<M; i++)
FFT_1D(ROW[i]，N);
for (int j=0; j<N; j++)
FFT_1D(COL[j]，M);
其中，ROW[i]表示矩陣的第i行。注意這只是一個簡單的記法，並不能完全照抄。還需要通過一些語句來生成各行的數據。同理，COL[i]是對矩陣的第i列的一種簡單表示方法。
所以，關鍵是一維FFT演算法的實現。

2、常式：

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#defineN1000
/*定義復數類型*/
typedefstruct{
doublereal;
doubleimg;
}complex;
complexx[N],*W;/*輸入序列,變換核*/
intsize_x=0;/*輸入序列的大小，在本程序中僅限2的次冪*/
doublePI;/*圓周率*/
voidfft();/*快速傅里葉變換*/
voidinitW();/*初始化變換核*/
voidchange();/*變址*/
voidadd(complex,complex,complex*);/*復數加法*/
voidmul(complex,complex,complex*);/*復數乘法*/
voidsub(complex,complex,complex*);/*復數減法*/
voidoutput();
intmain(){
inti;/*輸出結果*/
system("cls");
PI=atan(1)*4;
printf("Pleaseinputthesizeofx:
");
scanf("%d",&size_x);
printf("Pleaseinputthedatainx[N]:
");
for(i=0;i<size_x;i++)
scanf("%lf%lf",&x[i].real,&x[i].img);
initW();
fft();
output();
return0;
}
/*快速傅里葉變換*/
voidfft(){
inti=0,j=0,k=0,l=0;
complexup,down,proct;
change();
for(i=0;i<log(size_x)/log(2);i++){/*一級蝶形運算*/
l=1<<i;
for(j=0;j<size_x;j+=2*l){/*一組蝶形運算*/
for(k=0;k<l;k++){/*一個蝶形運算*/
mul(x[j+k+l],W[size_x*k/2/l],&proct);
add(x[j+k],proct,&up);
sub(x[j+k],proct,&down);
x[j+k]=up;
x[j+k+l]=down;
}
}
}
}
/*初始化變換核*/
voidinitW(){
inti;
W=(complex*)malloc(sizeof(complex)*size_x);
for(i=0;i<size_x;i++){
W[i].real=cos(2*PI/size_x*i);
W[i].img=-1*sin(2*PI/size_x*i);
}
}
/*變址計算，將x(n)碼位倒置*/
voidchange(){
complextemp;
unsignedshorti=0,j=0,k=0;
doublet;
for(i=0;i<size_x;i++){
k=i;j=0;
t=(log(size_x)/log(2));
while((t--)>0){
j=j<<1;
j|=(k&1);
k=k>>1;
}
if(j>i){
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
}
/*輸出傅里葉變換的結果*/
voidoutput(){
inti;
printf("Theresultareasfollows
");
for(i=0;i<size_x;i++){
printf("%.4f",x[i].real);
if(x[i].img>=0.0001)printf("+%.4fj
",x[i].img);
elseif(fabs(x[i].img)<0.0001)printf("
");
elseprintf("%.4fj
",x[i].img);
}
}
voidadd(complexa,complexb,complex*c){
c->real=a.real+b.real;
c->img=a.img+b.img;
}
voidmul(complexa,complexb,complex*c){
c->real=a.real*b.real-a.img*b.img;
c->img=a.real*b.img+a.img*b.real;
}
voidsub(complexa,complexb,complex*c){
c->real=a.real-b.real;
c->img=a.img-b.img;
}

⑸ 計算機圖形學直線段裁剪演算法或二維基本變換演算法，能復制運行的來啊，謝謝大俠們了 啊

#include"graphics.h"
#include"math.h"
typedef struct Point /* 點 */
{
int x;
int y;
}Point;
/* 點的平移變換 */
void PinYi(int * x,int * y,int tx,int ty)
{
*x = *x + tx;
*y = *y + ty;
}
/* 點的旋轉變換 */
void XuanZhuan(int * x,int * y,float q)
{
int m ;
int n;
float Q;
Q = (3.1415926/180)*q;
m = (*x);
n = (*y);
*x = m * cos(Q) - n * sin(Q);
*y = m * sin(Q) + n * cos(Q);
}
void XuanZhuan_RY(int m,int n,int * x,int * y,float q)/* 繞(m,n)的旋轉*/
{

PinYi(x,y,-m,-n);
XuanZhuan(x,y,q);
PinYi(x,y,m,n);
}
void line_dda(int x1,int y1,int x2,int y2 ,COLORREF color)
{
float x = 0.0;
float y = 0.0;
float x3 = ( float )x1;
float y3 = ( float )y1;
float n;
n=( float )( abs( x2-x1 ) >= abs( y2-y1 ) ? abs( x2-x1 ) : abs( y2-y1 ) );
if( n != 0.0 )
{
x=( ( float )( x2-x1 ) ) / n;
y=( ( float )( y2-y1 ) ) / n;
}
while( n >= 0 )
{
putpixel( ( int )x3 , ( int )y3 , color );
x3 += x ;y3 += y ;n -= 1.0;
}
}
void line(Point i,Point j,COLORREF color){
line_dda(i.x,i.y,j.x,j.y,color);
}
Point p[4]={-50,50,50,50,-50,-50,50,-50};
int PY[2]={0,0},XZ=0;
void main()
{
int width=600,height=480;
int zbx=200,zby=200;
COLORREF color=0x00ff00;
char ch;
initgraph(width, height);
ch=getch();
for(int o=0;o<4;o++)
PinYi(&p[o].x,&p[o].y,zbx,zby);
while(ch=getch())
{
PY[0]=0;PY[1]=0;
XZ=0;
switch(ch){
case 'q': XZ--;break;
case 'e': XZ++;break;
case 'w': PY[1]--;break;
case 's': PY[1]++;break;
case 'a': PY[0]--;break;
case 'd': PY[0]++;break;
//default :return 0;
}
for(int o=0;o<4;o++)
{
PinYi(&p[o].x,&p[o].y,PY[0],PY[1]);
PinYi(&zbx,&zby,PY[0],PY[1]);
XuanZhuan_RY(zbx,zby,&p[o].x,&p[o].y,XZ);
}
cleardevice();
line(p[0],p[1],color);
line(p[1],p[2],color);
line(p[2],p[3],color);
line(p[3],p[0],color);
}
}

有個問題是，，旋轉的時候因為π取的3.1415926七位，所以越轉越小！！！
需要改動！！就不弄了，要睡了！！

⑹ 試討論一維DCT、二維DCT變換不採用快速演算法時所需的加法、乘法次數。

【答案】：(1)一維DCT：
Y=AX
對每一個變換系數Y(K)，需作N次乘法，N-1次加法。共有N個變換系數，需N²次乘法，N(N-1)次加法。
(2)二維DCT：
F=[DCT]，[DCT]^T
對每一個變換系數Y(u，v)，需作2次矩陣的相乘。每次相乘需N次乘法，N-1次加法，所以要得到Y(u，v)，需2N次乘法，2(N-1)次加法。共有N²個變換系數(N×N像素塊)，因此共需2N³次乘法，2N²(N-1)次加法。