本文目录一览：
求C语言代码解释！！！望高手指点。。。
#includegraphics.h //引用头文件 不写会影响一些函数的使用
#includestdio.h
#includestdlib.h
#includeconio.h
#define IMAGE_SIZE 10 //宏定义 在下面的代码中出现 IMAGE_SIZE 就用10 代替就可以
void draw_image(int x,int y); //函数声明 下面有具体函数定义 没声明 就不可以用这个函数
void putstar(void); //同上
main() //主函数
{
int driver=DETECT;
int mode,color;
void *pt_addr;
int x,y,maxy,maxx,midy,midx,i;
unsigned size;
initgraph(driver,mode,"");
maxx=getmaxx(); //调用函数
maxy=getmaxy();
midx=maxx/2;
x=0;
midy=y=maxy/2;
settextstyle(TRIPLEX_FONT,HORIZ_DIR,4);
settextjustify(CENTER_TEXT,CENTER_TEXT);
outtextxy(midx,400,"AROUND THE WORLD");
setbkcolor(BLACK);
setcolor(RED);
setlinestyle(SOLID_LINE,0,THICK_WIDTH);
ellipse(midx,midy,130,50,160,30);
draw_image(x,y);
size=imagesize(x,y-IMAGE_SIZE,x+(4*IMAGE_SIZE),y+IMAGE_SIZE);
pt_addr=malloc(size);
getimage(x,y-IMAGE_SIZE,x+(4*IMAGE_SIZE),y+IMAGE_SIZE,pt_addr);
putstar();
setcolor(WHITE);
setlinestyle(SOLID_LINE,0,NORM_WIDTH);
rectangle(0,0,maxx,maxy);
while (!kbhit())
{
putstar();
setcolor(RED);
setlinestyle(SOLID_LINE,0,THICK_WIDTH);
ellipse(midx,midy,130,50,160,30);
setcolor(BLACK);
ellipse(midx,midy,130,50,160,30);
for (i=0;i=13;i++)
{
setcolor(i%2==0 ? LIGHTBLUE:BLACK);
ellipse(midx,midy,0,360,100-8*i,100);
setcolor(LIGHTBLUE);
ellipse(midx,midy,0,360,100,100-8*i);
}
putimage(x,y-IMAGE_SIZE,pt_addr,XOR_PUT);
x=x=maxx?0:x+6;
putimage(x,y-IMAGE_SIZE,pt_addr,COPY_PUT);
}
free(pt_addr);
closegraph();
return;
}
void draw_image(int x,int y) //函数定义 构造一个函数 传入两个参数 利用两个参数求出数组 arw10个元素
{
int arw[11];
arw[0]=x+10; arw[1]=y-10;
arw[2]=x+34; arw[3]=y-6;
arw[4]=x+34; arw[5]=y+6;
arw[6]=x+10; arw[7]=y+10;
arw[8]=x+10; arw[9]=y-10;
moveto(x+10,y-4); //这个函数在这个程序里没有定义过却直接使用 所以可能在头文件中定义过
setcolor(14); //同上
setfillstyle(1,4); //同上
linerel(-3*10,-2*8); //同上
moveto(x+10,y+4); //同上
linerel(-3*10,+2*8); //同上
moveto(x+10,y); //同上
linerel(-3*10,0); //同上
setcolor(3); //同上
setfillstyle(1,LIGHTBLUE);//同上
fillpoly(4,arw); //同上
}
void putstar(void) //定义一个函数
{
int seed=1858; //随机种子 用于随机函数中
int i,dotx,doty,h,w,color,maxcolor;
maxcolor=getmaxcolor();
w=getmaxx();
h=getmaxy();
srand(seed); //调用随机函数 使其产生每次都不一样的结果
for(i=0;i250;++i)
{
dotx=i+random(w-1);
doty=1+random(h-1);
color=random(maxcolor);
setcolor(color);
putpixel(dotx,doty,color);
circle(dotx+1,doty+1,1);
}
srand(seed);
}
希望对你有帮助
c语言 图形函数
图形函数 1. 图形模式的初始化
不同的显示器适配器有不同的图形分辨率。即是同一显示器适配器, 在不同
模式下也有不同分辨率。因此, 在屏幕作图之前, 必须根据显示器适配器种类将
显示器设置成为某种图形模式, 在未设置图形模式之前, 微机系统默认屏幕为文
本模式(80列, 25行字符模式), 此时所有图形函数均不能工作。设置屏幕为图形
模式, 可用下列图形初始化函数:
void far initgraph(int far *gdriver, int far *gmode, char *path);
其中gdriver和gmode分别表示图形驱动器和模式, path是指图形驱动程序所
在的目录路径。有关图形驱动器、图形模式的符号常数及对应的分辨率见表2。
图形驱动程序由Turbo C出版商提供, 文件扩展名为.BGI。根据不同的图形
适配器有不同的图形驱动程序。例如对于EGA、 VGA 图形适配器就调用驱动程序
EGAVGA.BGI。 例4. 使用图形初始化函数设置VGA高分辨率图形模式
#include graphics.h
int main()
{
int gdriver, gmode;
gdriver=VGA;
gmode=VGAHI;
initgraph(gdriver, gmode, "c:\\tc");
bar3d(100, 100, 300, 250, 50, 1); /*画一长方体*/
getch();
closegraph();
return 0;
}
有时编程者并不知道所用的图形显示器适配器种类, 或者需要将编写的程序
用于不同图形驱动器, Turbo C提供了一个自动检测显示器硬件的函数, 其调用
格式为:
void far detectgraph(int *gdriver, *gmode);
其中gdriver和gmode的意义与上面相同。
例5. 自动进行硬件测试后进行图形初始化
#include graphics.h
int main()
{
int gdriver, gmode;
detectgraph(gdriver, gmode); /*自动测试硬件*/
printf("the graphics driver is %d, mode is %d\n", gdriver,
gmode); /*输出测试结果*/
getch();
initgraph(gdriver, gmode, "c:\\tc");
/* 根据测试结果初始化图形*/
bar3d(10, 10, 130, 250, 20, 1);
getch();
closegraph();
return 0;
}
上例程序中先对图形显示器自动检测, 然后再用图形初始化函数进行初始化
设置, 但Turbo C提供了一种更简单的方法, 即用gdriver= DETECT 语句后再跟
initgraph()函数就行了。采用这种方法后, 上例可改为:
例6.
#include graphics.h
int main()
{
int gdriver=DETECT, gmode;
initgraph(gdriver, gmode, "c:\\tc");
bar3d(50, 50, 150, 30, 1);
getch();
closegraph();
return 0;
}
另外, Turbo C提供了退出图形状态的函数closegraph(), 其调用格式为:
void far closegraph(void);
调用该函数后可退出图形状态而进入文本方式(Turbo C 默认方式), 并释放
用于保存图形驱动程序和字体的系统内存。
2. 独立图形运行程序的建立
Turbo C对于用initgraph()函数直接进行的图形初始化程序, 在编译和链接
时并没有将相应的驱动程序(*.BGI)装入到执行程序, 当程序进行到intitgraph()
语句时, 再从该函数中第三个形式参数char *path中所规定的路径中去找相应的
驱动程序。若没有驱动程序, 则在C:\TC中去找, 如C:\TC中仍没有或TC不存在,
将会出现错误:
BGI Error: Graphics not initialized (use 'initgraph')
因此, 为了使用方便, 应该建立一个不需要驱动程序就能独立运行的可执行
图形程序,Turbo C中规定用下述步骤(这里以EGA、VGA显示器为例):
1. 在C:\TC子目录下输入命令:BGIOBJ EGAVGA
此命令将驱动程序EGAVGA.BGI转换成EGAVGA.OBJ的目标文件。
2. 在C:\TC子目录下输入命令:TLIB LIB\GRAPHICS.LIB+EGAVGA
此命令的意思是将EGAVGA.OBJ的目标模块装到GRAPHICS.LIB库文件中。
3. 在程序中initgraph()函数调用之前加上一句:
registerbgidriver(EGAVGA_driver):
该函数告诉连接程序在连接时把EGAVGA的驱动程序装入到用户的执行程序中。
经过上面处理,编译链接后的执行程序可在任何目录或其它兼容机上运行。
假设已作了前两个步骤,若再向例6中加 registerbgidriver()函数则变成:
例7:
#includestdio.h
#includegraphics.h
int main()
{
int gdriver=DETECT,gmode;
registerbgidriver(EGAVGA_driver): / *建立独立图形运行程序 */
initgraph( gdriver, gmode,"c:\\tc");
bar3d(50,50,250,150,20,1);
getch();
closegraph();
return 0;
}
上例编译链接后产生的执行程序可独立运行。
如不初始化成EGA或CGA分辨率, 而想初始化为CGA分辨率, 则只需要将上述
步骤中有EGAVGA的地方用CGA代替即可。
3.屏幕颜色的设置和清屏函数
对于图形模式的屏幕颜色设置, 同样分为背景色的设置和前景色的设置。在
Turbo C中分别用下面两个函数。
设置背景色: void far setbkcolor( int color);
设置作图色: void far setcolor(int color);
其中color 为图形方式下颜色的规定数值, 对EGA, VGA显示器适配器, 有关
颜色的符号常数及数值见下表所示。
表3 有关屏幕颜色的符号常数表
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
符号常数 数值 含义 符号常数 数值 含义
———————————————————————————————————
BLACK 0 黑色 DARKGRAY 8 深灰
BLUE 1 兰色 LIGHTBLUE 9 深兰
GREEN 2 绿色 LIGHTGREEN 10 淡绿
CYAN 3 青色 LIGHTCYAN 11 淡青
RED 4 红色 LIGHTRED 12 淡红
MAGENTA 5 洋红 LIGHTMAGENTA 13 淡洋红
BROWN 6 棕色 YELLOW 14 黄色
LIGHTGRAY 7 淡灰 WHITE 15 白色
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
对于CGA适配器, 背景色可以为表3中16种颜色的一种, 但前景色依赖于不同
的调色板。共有四种调色板, 每种调色板上有四种颜色可供选择。不同调色板所
对应的原色见表4。
表4 CGA调色板与颜色值表
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
调色板 颜色值
——————————— ——————————————————
符号常数 数值 0 1 2 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
C0 0 背景 绿 红 黄
C1 1 背景 青 洋红 白
C2 2 背景 淡绿 淡红 黄
C3 3 背景 淡青 淡洋红 白
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
清除图形屏幕内容使用清屏函数, 其调用格式如下:
voide far cleardevice(void);
另外, TURBO C也提供了几个获得现行颜色设置情况的函数。
int far getbkcolor(void); 返回现行背景颜色值。
int far getcolor(void); 返回现行作图颜色值。
int far getmaxcolor(void); 返回最高可用的颜色值。
4. 基本图形函数
基本图形函数包括画点, 线以及其它一些基本图形的函数。本节对这些函数
作一全面的介绍。
一、画点
1. 画点函数
void far putpixel(int x, int y, int color);
该函数表示有指定的象元画一个按color所确定颜色的点。对于颜色color的
值可从表3中获得而对x, y是指图形象元的坐标。
在图形模式下, 是按象元来定义坐标的。对VGA适配器, 它的最高分辨率为
640x480, 其中640为整个屏幕从左到右所有象元的个数, 480 为整个屏幕从上到
下所有象元的个数。屏幕的左上角坐标为(0, 0), 右下角坐标为(639, 479), 水
平方向从左到右为x轴正向, 垂直方向从上到下为y轴正向。TURBO C 的图形函数
都是相对于图形屏幕坐标, 即象元来说的。
关于点的另外一个函数是:
int far getpixel(int x, int y);
它获得当前点(x, y)的颜色值。
2. 有关坐标位置的函数
int far getmaxx(void);
返回x轴的最大值。
int far getmaxy(void);
返回y轴的最大值。
int far getx(void);
返回游标在x轴的位置。
void far gety(void);
返回游标有y轴的位置。
void far moveto(int x, int y);
移动游标到(x, y)点, 不是画点, 在移动过程中亦画点。
void far moverel(int dx, int dy);
移动游标从现行位置(x, y)移动到(x+dx, y+dy)的位置, 移动过程中不画点。
二、画线
1. 画线函数
TURBO C提供了一系列画线函数, 下面分别叙述:
void far line(int x0, int y0, int x1, int y1);
画一条从点(x0, y0)到(x1, y1)的直线。
void far lineto(int x, int y);
画一作从现行游标到点(x, y)的直线。
void far linerel(int dx, int dy);
画一条从现行游标(x, y)到按相对增量确定的点(x+dx, y+dy)的直线。
void far circle(int x, int y, int radius);
以(x, y)为圆心, radius为半径, 画一个圆。
void far arc(int x, int y, int stangle, int endangle, int radius);
以(x, y)为圆心, radius为半径, 从stangle开始到endangle结束(用度表示)
画一段圆弧线。在TURBO C中规定x轴正向为0度, 逆时针方向旋转一周, 依次为
90, 180, 270和360度(其它有关函数也按此规定, 不再重述)。
void ellipse(int x, int y, int stangle, int endangle, int xradius,
int yradius);
以(x, y)为中心, xradius, yradius为x轴和y轴半径, 从角stangle 开始到
endangle结束画一段椭圆线, 当stangle=0, endangle=360时, 画出一个完整的
椭圆。
void far rectangle(int x1, int y1, int x2, inty2);
以(x1, y1)为左上角, (x2, y2)为右下角画一个矩形框。
void far drawpoly(int numpoints, int far *polypoints);
画一个顶点数为numpoints, 各顶点坐标由polypoints 给出的多边形。
polypoints整型数组必须至少有2倍顶点数个无素。每一个顶点的坐标都定义为x,
y, 并且x在前。值得注意的是当画一个封闭的多边形时, numpoints 的值取实际
多边形的顶点数加一, 并且数组polypoints中第一个和最后一个点的坐标相同。
下面举一个用drawpoly()函数画箭头的例子。
例9:
#includestdlib.h
#includegraphics.h
int main()
{
int gdriver, gmode, i;
int arw[16]={200, 102, 300, 102, 300, 107, 330,
100, 300, 93, 300, 98, 200, 98, 200, 102};
gdriver=DETECT;
registerbgidriver(EGAVGA_driver);
initgraph(gdriver, gmode, "");
setbkcolor(BLUE);
cleardevice();
setcolor(12); /*设置作图颜色*/
drawpoly(8, arw); /*画一箭头*/
getch();
closegraph();
return 0;
}
2. 设定线型函数
在没有对线的特性进行设定之前, TURBO C用其默认值, 即一点宽的实线,
但TURBO C也提供了可以改变线型的函数。线型包括:宽度和形状。其中宽度只有
两种选择: 一点宽和三点宽。而线的形状则有五种。下面介绍有关线型的设置函
数。
void far setlinestyle(int linestyle, unsigned upattern, int
thickness);
该函数用来设置线的有关信息, 其中linestyle是线形状的规定, 见表5。
表5. 有关线的形状(linestyle)
━━━━━━━━━━━━━━━━━━━━━━━━━
符号常数 数值 含义
—————————————————————————
SOLID_LINE 0 实线
DOTTED_LINE 1 点线
CENTER_LINE 2 中心线
DASHED_LINE 3 点画线
USERBIT_LINE 4 用户定义线
━━━━━━━━━━━━━━━━━━━━━━━━━
thickness是线的宽度, 见表6。
表6. 有关线宽(thickness)
━━━━━━━━━━━━━━━━━━━━━━━━━
符号常数 数值 含义
—————————————————————————
NORM_WIDTH 1 一点宽
THIC_WIDTH 3 三点宽
━━━━━━━━━━━━━━━━━━━━━━━━━
对于upattern, 只有linestyle选USERBIT_LINE 时才有意义( 选其它线型,
uppattern取0即可)。此进uppattern的16位二进制数的每一位代表一个象元, 如
果那位为1, 则该象元打开, 否则该象元关闭。
void far getlinesettings(struct linesettingstype far *lineinfo);
该函数将有关线的信息存放到由lineinfo 指向的结构中, 表中
linesettingstype的结构如下:
struct linesettingstype{
int linestyle;
unsigned upattern;
int thickness;
}
例如下面两句程序可以读出当前线的特性
struct linesettingstype *info;
getlinesettings(info);
void far setwritemode(int mode);
该函数规定画线的方式。如果mode=0, 则表示画线时将所画位置的原来信息
覆盖了(这是TURBO C的默认方式)。如果mode=1, 则表示画线时用现在特性的线
与所画之处原有的线进行异或(XOR)操作, 实际上画出的线是原有线与现在规定
的线进行异或后的结果。因此, 当线的特性不变, 进行两次画线操作相当于没有
画线。
有关线型设定和画线函数的例子如下所示。
例10.
#includestdlib.h
#includegraphics.h
int main()
{
int gdriver, gmode, i;
gdriver=DETECT;
registerbgidriver(EGAVGA_driver);
initgraph(gdriver, gmode, "");
setbkcolor(BLUE);
cleardevice();
setcolor(GREEN);
circle(320, 240, 98);
setlinestyle(0, 0, 3); /*设置三点宽实线*/
setcolor(2);
rectangle(220, 140, 420, 340);
setcolor(WHITE);
setlinestyle(4, 0xaaaa, 1); /*设置一点宽用户定义线*/
line(220, 240, 420, 240);
line(320, 140, 320, 340);
getch();
closegraph();
return 0;
}
5. 封闭图形的填充
填充就是用规定的颜色和图模填满一个封闭图形。
一、先画轮廓再填充
TURBO C提供了一些先画出基本图形轮廓, 再按规定图模和颜色填充整个封
闭图形的函数。在没有改变填充方式时, TURBO C以默认方式填充。 下面介绍这
些函数。
void far bar(int x1, int y1, int x2, int y2);
确定一个以(x1, y1)为左上角, (x2, y2)为右下角的矩形窗口, 再按规定图
模和颜色填充。
说明: 此函数不画出边框, 所以填充色为边框。
void far bar3d(int x1, int y1, int x2, int y2, int depth, int
topflag);
当topflag为非0时, 画出一个三维的长方体。当topflag为0时, 三维图形不
封顶, 实际上很少这样使用。
说明: bar3d()函数中, 长方体第三维的方向不随任何参数而变, 即始终为
45度的方向。
void far pieslice(int x, int y, int stangle, int endangle, int
radius);
画一个以(x, y)为圆心, radius为半径, stangle为起始角度, endangle 为
终止角度的扇形, 再按规定方式填充。当stangle=0, endangle=360 时变成一个
实心圆, 并在圆内从圆点沿X轴正向画一条半径。
void far sector(int x, int y, int stanle, intendangle, int
xradius, int yradius);
画一个以(x, y)为圆心分别以xradius, yradius为x轴和y轴半径, stangle
为起始角, endangle为终止角的椭圆扇形, 再按规定方式填充。
二、设定填充方式
TURBO C有四个与填充方式有关的函数。下面分别介绍:
void far setfillstyle(int pattern, int color);
color的值是当前屏幕图形模式时颜色的有效值。pattern的值及与其等价的
符号常数 除USER_FILL(用户定义填充式样)以外, 其它填充式样均可由setfillstyle()
函数设置。当选用USER_FILL时, 该函数对填充图模和颜色不作任何改变。 之所
以定义USER_FILL主要因为在获得有关填充信息时用到此项。
void far setfillpattern(char * upattern,int color);
设置用户定义的填充图模的颜色以供对封闭图形填充。
其中upattern是一个指向8个字节的指针。这8个字节定义了8x8点阵的图形。
每个字节的8位二进制数表示水平8点, 8个字节表示8行, 然后以此为模型向个封
闭区域填充。
void far getfillpattern(char * upattern);
该函数将用户定义的填充图模存入upattern指针指向的内存区域。
void far getfillsetings(struct fillsettingstype far * fillinfo);
获得现行图模的颜色并将存入结构指针变量fillinfo中。其中fillsettingstype
结构定义如下:
struct fillsettingstype{
int pattern; /* 现行填充模式 * /
int color; /* 现行填充模式 * /
};
三、任意封闭图形的填充
截止目前为止, 我们只能对一些特定形状的封闭图形进行填充, 但还不能对
任意封闭图形进行填充。为此, TURBO C 提供了一个可对任意封闭图形填充的函
数, 其调用格式如下:
void far floodfill(int x, int y, int border);
其中: x, y为封闭图形内的任意一点。border为边界的颜色, 也就是封闭图
形轮廓的颜色。调用了该函数后, 将用规定的颜色和图模填满整个封闭图形。例12:
#includestdlib.h
#includegraphics.h
main()
{
int gdriver, gmode;
strct fillsettingstype save;
gdriver=DETECT;
initgraph(gdriver, gmode, "");
setbkcolor(BLUE);
cleardevice();
setcolor(LIGHTRED);
setlinestyle(0,0,3);
setfillstyle(1,14); /*设置填充方式*/
bar3d(100,200,400,350,200,1); /*画长方体并填充*/
floodfill(450,300,LIGHTRED); /*填充长方体另外两个面*/
floodfill(250,150, LIGHTRED);
rectanle(450,400,500,450); /*画一矩形*/
floodfill(470,420, LIGHTRED); /*填充矩形*/
getch();
closegraph();
}
6. 有关图形窗口和图形屏幕操作函数
一、图形窗口操作
象文本方式下可以设定屏幕窗口一样, 图形方式下也可以在屏幕上某一区域
设定窗口, 只是设定的为图形窗口而已, 其后的有关图形操作都将以这个窗口的
左上角(0,0)作为坐标原点, 而且可为通过设置使窗口之外的区域为不可接触。
这样, 所有的图形操作就被限定在窗口内进行。
void far setviewport(int xl,int yl,int x2, int y2,int clipflag);
设定一个以(xl,yl)象元点为左上角, (x2,y2)象元为右下角的图形窗口, 其
中x1,y1,x2,y2是相对于整个屏幕的坐标。若clipflag为非0, 则设定的图形以外
部分不可接触, 若clipflag为0, 则图形窗口以外可以接触。
void far clearviewport(void);
清除现行图形窗口的内容。
void far getviewsettings(struct viewporttype far * viewport);
获得关于现行窗口的信息,并将其存于viewporttype定义的结构变量viewport
中, 其中viewporttype的结构说明如下:
struct viewporttype{
int left, top, right, bottom;
int cliplag;
};
二、屏幕操作
除了清屏函数以外, 关于屏幕操作还有以下函数:
void far setactivepage(int pagenum);
void far setvisualpage(int pagenum);
这两个函数只用于EGA,VGA 以及HERCULES图形适配器。setctivepage() 函数
是为图形输出选择激活页。 所谓激活页是指后续图形的输出被写到函数选定的
pagenum页面, 该页面并不一定可见。setvisualpage()函数才使pagenum 所指定
的页面变成可见页。页面从0开始(Turbo C默认页)。如果先用setactivepage()
函数在不同页面上画出一幅幅图像,再用setvisualpage()函数交替显示, 就可以
实现一些动画的效果。
void far getimage(int xl,int yl, int x2,int y2, void far *mapbuf);
void far putimge(int x,int,y,void * mapbuf, int op);
unsined far imagesize(int xl,int yl,int x2,int y2);
这三个函数用于将屏幕上的图像复制到内存,然后再将内存中的图像送回到
屏幕上。首先通过函数imagesize()测试要保存左上角为(xl,yl), 右上角为(x2,
y2)的图形屏幕区域内的全部内容需多少个字节, 然后再给mapbuf 分配一个所测
数字节内存空间的指针。通过调用getimage()函数就可将该区域内的图像保存在
内存中, 需要时可用putimage()函数将该图像输出到左上角为点(x, y)的位置上,
其中getimage()函数中的参数op规定如何释放内存中图像。
对于imagesize()函数, 只能返回字节数小于64K字节的图像区域, 否则将会
出错, 出错时返回-1。
本节介绍的函数在图像动画处理、菜单设计技巧中非常有用。
例13: 下面程序模拟两个小球动态碰撞过程。
7. 图形模式下的文本输出
在图形模式下, 只能用标准输出函数, 如printf(), puts(), putchar() 函
数输出文本到屏幕。除此之外, 其它输出函数(如窗口输出函数)不能使用, 即是
可以输出的标准函数, 也只以前景色为白色, 按80列, 25行的文本方式输出。
Turbo C2.0也提供了一些专门用于在图形显示模式下的文本输出函数。下面
将分别进行介绍。
一、文本输出函数
void far outtext(char far *textstring);
该函数输出字符串指针textstring所指的文本在现行位置。
void far outtextxy(int x, int y, char far *textstring);
该函数输出字符串指针textstring所指的文本在规定的(x, y)位置。 其中x
和y为象元坐标。
说明:
这两个函数都是输出字符串, 但经常会遇到输出数值或其它类型的数据,
此时就必须使用格式化输出函数sprintf()。
sprintf()函数的调用格式为:
int sprintf(char *str, char *format, variable-list);
它与printf()函数不同之处是将按格式化规定的内容写入str 指向的字符串
中, 返回值等于写入的字符个数。
例如:
sprintf(s, "your TOEFL score is %d", mark);
这里s应是字符串指针或数组, mark为整型变量。
如何用Python编写一个素数环
此文主要目的，是向大家展示如何才能用python语言，来部署STARK算法。
STARKs（可扩容的透明知识论证）是创建一种证明的技术，这项证明中f(x)=y，其中f可能要花很长的时间来进行计算，但是这个证明可以被很快验证。STARK是“双重扩容”：对于一个需要t步骤的计算，这会花费大约O(t * log(t))步骤才能完成这个证明，这可能是最优的情况，而且这需要通过~O(log2(t))个步骤才能验证，对于中等大小的T值，它比原始计算快得多。STARKs也拥有隐私保护的“零知识证明”的特性，虽然我们将这类使用案例应用到其中，从而完成可验证的延迟功能，不需要这类性质，所以我们不用担心。
首先，先请几项说明：
这个代码还没有完全审核；在实际使用案例中的情况，还不能保证
这部分代码是还没有达到理想状态（是用Python语言写的）
STARKs 的“真实情况” 倾向于使用二进制字段而不是素数域的特定应用程序效率的原因；但是，他们确实也表现出，这里写出的代码是合法并且可用的。
没有一个真实的方法来使用STARK。它是一个非常宽泛的加密和数学架构，同时为不同的应用有不同的设置，以及连续的研究来减少证明者和验证者的复杂性，同时提高可用性。
此文希望大家能够知道，模运算和素数域是如何运行的，
并且和多项式概念，插值和估值进行结合。
现在，让我们一起来了解吧！
MIMC
下面是STARK的功能展示：
def mimc(inp, steps, round_constants): start_time = time.time() for i in range(steps-1): inp = (inp**3 + round_constants[i % len(round_constants)]) % modulus print("MIMC computed in %.4f sec" % (time.time() - start_time)) return inp
我们选择MIMC作为案例，因为它（i）很容易理解，（ii）在真实世界使用的很多。函数功能见下图：
注意：在很多关于MIMC的讨论中，你可以典型地看出使用了XOR，而不是+；这是因为MIMC可以在二进制情况下使用，其中添加是XOR；这里我们会在素数领域进行。
在我们的案例中，常数相对而言会是比较小的列表（例如，64位），这会一直连续地进行周期循环（也就说，在k[64]之后）。MIMC自身可以获得这个特性，因为MIMC可以向后进行计算（从相应的输出获得输入），但是往后计算需要比向前计算多花费100倍的时间（并且没有方向可以同步进行）。所以你可以将往后计算的功能想象成计算不能同步的工作量证明，并且往前方向计算的功能可以作为验证的过程。
x - x(2p-1)/3 是x - x3 的反函数；根据费马小定理，这是真实的，尽管这个定理没有费马大定理出名，但是依然对数学的贡献很大。
我们尝试使用STARK来进行更加有效的验证，而不是让验证者必须在向前方向运行MIMC，在完成向后计算之后，证明者可以在向前方向进行STARK计算，并且验证者可以很简单地验证STARK。我们希望计算STARK可以比MIMC向前和向后之间的运行速度差别要小，所以证明者的时间仍然是有初始的向后计算来主导的。而并不是STARK计算。STARK的认证会相对较快（在python语言算法中，可以是0.05-0.3秒），不论初始的计算时间有多长。
所有的计算会在2256 – 351 * 232 + 1个模内完成；我们使用素数模，因为它是小于2256 最大的素数，其中乘法群包含了232 个子集（也就是说，有这样一个数g，从而在完全232次循环之后，G素数环的连续幂模绕回到1），而且是按照6k+5的形式。首个特性是保证FFT和FRI算法的有效版本，其次是保证MIMC实际上可以向后计算（请见上面提到的x - x(2p-1)/3 使用方法）。
素域操作
我们通过建立方便的等级来进行素域的操作，同时也有多项式的操作。代码如下，收首先是小数位数：
class PrimeField(): def __init__(self, modulus): # Quick primality test assert pow(2, modulus, modulus) == 2 self.modulus = modulus def add(self, x, y): return (x+y) % self.modulus def sub(self, x, y): return (x-y) % self.modulus def mul(self, x, y): return (x*y) % self.modulus
并且使用扩展欧几里得算法，来计算模块逆转（这和在素域中计算1/x相同）：
# Modular inverse using the extended Euclidean algorithm def inv(self, a): if a == 0: return 0 lm, hm = 1, 0 low, high = a % self.modulus, self.modulus while low 1: r = high//low nm, new = hm-lm*r, high-low*r lm, low, hm, high = nm, new, lm, low return lm % self.modulus
上面的算法是相对昂贵的；幸运地是，对于特定的案例，我们需要做很多的模逆计算，有一个数学方法可以让我们来计算很多逆运算，被称为蒙哥马利批量求逆：
使用蒙哥马利批量求逆来计算模逆，其输入为紫色，输出为绿色，乘法门为黑色，红色方块是唯一的模逆。
下面的代码是算法的体现，其中包含一些特别的逻辑。如果我们正在求逆的集合中包含零，那么它会将这些零的逆设置为 0 并继续前进。
def multi_inv(self, values): partials = [1] for i in range(len(values)): partials.append(self.mul(partials[-1], values[i] or 1)) inv = self.inv(partials[-1]) outputs = [0] * len(values) for i in range(len(values), 0, -1): outputs[i-1] = self.mul(partials[i-1], inv) if values[i-1] else 0 inv = self.mul(inv, values[i-1] or 1) return outputs
这部分算法接下来会验证称为非常重要的东西，特别是当我们开始和不同阶的多项式进行计算的时候。
现在我们来看看一些多项式计算。我们把多项式当做一个数据集，其中的i是第i阶（例如，x3 + 2x + 1变成[1, 2, 0, 1]）。下面就是在一个点进行多项式估算的方法：
# Evaluate a polynomial at a point def eval_poly_at(self, p, x): y = 0 power_of_x = 1 for i, p_coeff in enumerate(p): y += power_of_x * p_coeff power_of_x = (power_of_x * x) % self.modulus return y % self.modulus
困难和挑战
f.eval_poly_at([4, 5, 6], 2)的输出是多少？模是31吗？
下面的解释就是答案
.其实也有代码是多项式加法，减法，乘法和除法；这是很长的加减乘除运算。有一个很重要的内容是拉格朗日插值，它将一组 x 和 y 坐标作为输入，并返回通过所有这些点的最小多项式（你可以将其视为多项式求值的逆）：
# Build a polynomial that returns 0 at all specified xs def zpoly(self, xs): root = [1] for x in xs: root.insert(0, 0) for j in range(len(root)-1): root[j] -= root[j+1] * x return [x % self.modulus for x in root] def lagrange_interp(self, xs, ys): # Generate master numerator polynomial, eg. (x - x1) * (x - x2) * ... * (x - xn) root = self.zpoly(xs) # Generate per-value numerator polynomials, eg. for x=x2, # (x - x1) * (x - x3) * ... * (x - xn), by dividing the master # polynomial back by each x coordinate nums = [self.div_polys(root, [-x, 1]) for x in xs] # Generate denominators by evaluating numerator polys at each x denoms = [self.eval_poly_at(nums[i], xs[i]) for i in range(len(xs))] invdenoms = self.multi_inv(denoms) # Generate output polynomial, which is the sum of the per-value numerator # polynomials rescaled to have the right y values b = [0 for y in ys] for i in range(len(xs)): yslice = self.mul(ys[i], invdenoms[i]) for j in range(len(ys)): if nums[i][j] and ys[i]: b[j] += nums[i][j] * yslice return [x % self.modulus for x in b]
相关数学知识请参见此文的M-N部分。需要注意，我们也会有特别的方法lagrange_interp_4和lagrange_interp_2来加速次数小于 2 的拉格朗日插值和次数小于 4 的多项式运算。
快速傅立叶变换
如果你仔细阅读上面的算法，你也许会发现拉格朗日插值和多点求值（即求在N个点处次数小于N的多项式的值）都需要耗费2次时间，例如对于1000个点求拉格朗日插值，需要几百万个步骤，而且100万个点的拉格朗日插值需要万亿个步骤。这是不可接受的低效率，所以我们需要使用更加有效的算法，快速傅立叶变换。
FFT只需要花费O(n * log(n))的时间（也就是说，1000个点的计算需要10,000步，100万个点的计算需要2000步），虽然它的范围更受限制；x坐标必须是单位根部的完全集合，必须满足N = 2k 阶。也就是说，如果有N个点，那么x坐标必须某个P值的连续幂，1, p, p2, p3…，其中pN = 1。这个算法能够用来进行多点计算和插值计算，而且只需要调整一个小参数。
下面就是算法详情（这是个简单的表达方式；更详细内容可以参阅此处代码）
def fft(vals, modulus, root_of_unity): if len(vals) == 1: return vals L = fft(vals[::2], modulus, pow(root_of_unity, 2, modulus)) R = fft(vals[1::2], modulus, pow(root_of_unity, 2, modulus)) o = [0 for i in vals] for i, (x, y) in enumerate(zip(L, R)): y_times_root = y*pow(root_of_unity, i, modulus) o[i] = (x+y_times_root) % modulus o[i+len(L)] = (x-y_times_root) % modulus return o def inv_fft(vals, modulus, root_of_unity): f = PrimeField(modulus) # Inverse FFT invlen = f.inv(len(vals)) return [(x*invlen) % modulus for x in fft(vals, modulus, f.inv(root_of_unity))]
你可以自己通过一些输入来运行代码，并且看看是否能得到想要的结果，当你使用eval_poly_at的时候，给出你期望得到的答案。例如：
fft.fft([3,1,4,1,5,9,2,6], 337, 85, inv=True) [46, 169, 29, 149, 126, 262, 140, 93] f = poly_utils.PrimeField(337) [f.eval_poly_at([46, 169, 29, 149, 126, 262, 140, 93], f.exp(85, i)) for i in range(8)] [3, 1, 4, 1, 5, 9, 2, 6]
傅里叶变换会把[x[0] …. x[n-1]]作为输入，并且它的目标是输出x[0] + x[1] + … + x[n-1]作为首个元素，x[0] + x[1] * 2 + … + x[n-1] * w**(n-1)作为第二个元素，等等；快速傅里叶变换可以通过把数据分为两半，来完成这个，在两边都进行FFT，然后将结果结合在一起。
上图就是信息如何进行FFT运算的解释。请注意FFT是如何进行两次数据复制，并且进行粘合，直到你得到一个元素。
现在，我们把所有部分组合起来，看看整件事情是如何：def mk_mimc_proof(inp, steps, round_constants)，它生成运行 MIMC 函数的执行结果的证明，其中给定的输入为步骤数。首先，是一些 assert 函数：
# Calculate the set of x coordinates xs = get_power_cycle(root_of_unity, modulus) column = [] for i in range(len(xs)//4): x_poly = f.lagrange_interp_4( [xs[i+len(xs)*j//4] for j in range(4)], [values[i+len(values)*j//4] for j in range(4)], ) column.append(f.eval_poly_at(x_poly, special_x))
扩展因子是我们将要拉伸的计算轨迹（执行 MIMC 函数的“中间值”的集合）。
m2 = merkelize(column) # Pseudo-randomly select y indices to sample # (m2[1] is the Merkle root of the column) ys = get_pseudorandom_indices(m2[1], len(column), 40) # Compute the Merkle branches for the values in the polynomial and the column branches = [] for y in ys: branches.append([mk_branch(m2, y)] + [mk_branch(m, y + (len(xs) // 4) * j) for j in range(4)])
我们需要步数乘以扩展因子最多为 2^32，因为当 k 32 时，我们没有 2^k 次的单位根。
computational_trace_polynomial = inv_fft(computational_trace, modulus, subroot) p_evaluations = fft(computational_trace_polynomial, modulus, root_of_unity)
我们首个计算会是得出计算轨迹；也就是说，所有的计算中间值，从输入到输出。
assert steps = 2**32 // extension_factor assert is_a_power_of_2(steps) and is_a_power_of_2(len(round_constants)) assert len(round_constants) steps
然后，我们会从将计算轨迹转换为多项式，在单位根 g （其中，g^steps = 1）的连续幂的轨迹上“放下”连续值，然后我们对更大的集合——即单位根 g2 的连续幂，其中 g2^steps * 8 = 1（注意 g2^8 = g）的多项式求值。
# Generate the computational trace computational_trace = [inp] for i in range(steps-1): computational_trace.append((computational_trace[-1]**3 + round_constants[i % len(round_constants)]) % modulus) output = computational_trace[-1]
黑色： g1 的幂。紫色： g2 的幂。橙色：1。你可以将连续的单位根看作一个按这种方式排列的圆圈。我们沿着 g1的幂“放置”计算轨迹，然后扩展它来计算在中间值处（即 g2 的幂）的相同多项式的值。
我们可以将MIMC的循环常数转换为多项式。因为这些循环常数链是非常通常发生地（在我们的测试中，每64个步骤都会进行），最终证明他们形成了64阶的多项式，而且外面可以很容易计算出它的表达式，以及扩展式：
skips2 = steps // len(round_constants) constants_mini_polynomial = fft(round_constants, modulus, f.exp(subroot, skips2), inv=True) constants_polynomial = [0 if i % skips2 else constants_mini_polynomial[i//skips2] for i in range(steps)] constants_mini_extension = fft(constants_mini_polynomial, modulus, f.exp(root_of_unity, skips2))
假设其中有8192个步骤，并且有64个循环常数。这是我们想要做的：我们正在进行FFT，从而计算循环常数来作为g1128 的功能。然后我们在之间加入很多零，来完成g1本身的功能。因为g1128 大约每64步进行循环，我们知道g1这个功能也会同样。我们只计算这个扩展中的512个步骤，因为我们知道这个扩展会在每512步之后重复。现在，我们按照斐波那契案例中那样，计算C(P(x))，除了这次是计算，需要注意，我们不在计算使用系数形式的多项式；而是根据高次单位根的连续幂来对多项式进行求值。
c_of_p需要满足Q(x) = C(P(x), P(g1*x)，K(x)) = P(g1*x) – P(x)**3 – K(x)；目标是对于任何我们放入计算轨道的x（除了最后一步，因为在最后一步之后，就没有步骤），计算轨迹中的下个数值就和之前的相等，再加上循环常量。与第1部分中的斐波那契示例不同，其中如果某个计算步骤是在k向量，下个就会是k+1向量，我们把低次单位根（ g1 ）的连续幂放下计算轨迹，所以如果某个计算步骤是在x = g1i ，下个步骤就会在g1i+1 = g1i * g1 = x * g1。因此，对于低阶单位根（ g1 ）的每一个幂，我们希望最终会是P(x*g1) = P(x)**3 + K(x)，或者P(x*g1) – P(x)**3 – K(x) = Q(x) = 0。因此，Q(x) 会在低次单位根 g 的所有连续幂上等于零（除了最后一个）。
# Create the composed polynomial such that # C(P(x), P(g1*x), K(x)) = P(g1*x) - P(x)**3 - K(x) c_of_p_evaluations = [(p_evaluations[(i+extension_factor)%precision] - f.exp(p_evaluations[i], 3) - constants_mini_extension[i % len(constants_mini_extension)]) % modulus for i in range(precision)] print('Computed C(P, K) polynomial')
有个代数定理证明，如果Q(x)在所有这些x坐标，都等于零，那么最小多项式的乘积就会在所有这些x坐标等于零：Z(x) = (x – x_1) * (x – x_2) * … * (x – x_n)。通过证明在任何单个的坐标，Q(x)是等于零，我们想要证明这个很难，因为验证这样的证明比运行原始计算需要耗费更长的时间，我们会使用一个间接的方式来证明Q(x)是Z(x)的乘积。并且我们会怎么做呢？通过证明D(x) = Q(x) / Z(x)，并且使用FRI来证明它其实是个多项式，而不是个分数。
我们选择低次单位根和高次单位根的特定排列，因为事实证明，计算Z(x)，而且除以Z(x)也十分简单：Z 的表达式是两项的一部分。
需要注意地是，直接计算Z的分子和分母，然后使用批量模逆的方法将除以Z转换为乘法，随后通过 Z(X) 的逆来逐点乘以 Q(x) 的值。需要注意，对于低次单位根的幂，除了最后一个，都可以得到Z(x) = 0，所以这个计算包含其逆计算就会中断。这是非常不幸的，虽然我们会通过简单地修改随机检查和FRI算法来堵住这个漏洞，所以就算我们计算错误，也没关系。
因为Z(x)可以简洁地表达，我们也可以获得另个好处：验证者对于任何特别的x，可以快速计算Z(x)，而且还不需要任何提前计算。对于证明者来说，我们可以接受证明者必须处理大小等于步数的多项式，但我们不想让验证者做同样的事情，因为我们希望验证过程足够简洁。
# Compute D(x) = Q(x) / Z(x) # Z(x) = (x^steps - 1) / (x - x_atlast_step) z_num_evaluations = [xs[(i * steps) % precision] - 1 for i in range(precision)] z_num_inv = f.multi_inv(z_num_evaluations) z_den_evaluations = [xs[i] - last_step_position for i in range(precision)] d_evaluations = [cp * zd * zni % modulus for cp, zd, zni in zip(c_of_p_evaluations, z_den_evaluations, z_num_inv)] print('Computed D polynomial')
在几个随机点上，进行概念检测D(x) * Z(x) = Q(x)，从而可以验证转账约束，每个计算步骤是之前步骤的有效结果。但是我们也想验证边界约束，其中计算的输入和输出就是证明者所说的那样。只是要求证明者提供P(1), D(1), P(last_step)还有D(last_step)的数值，这些都是很脆弱的；没有证明，那些数值都是在同个多项式。所以，我们使用类似的多项式除法技巧：
# Compute interpolant of ((1, input), (x_atlast_step, output)) interpolant = f.lagrange_interp_2([1, last_step_position], [inp, output]) i_evaluations = [f.eval_poly_at(interpolant, x) for x in xs] zeropoly2 = f.mul_polys([-1, 1], [-last_step_position, 1]) inv_z2_evaluations = f.multi_inv([f.eval_poly_at(quotient, x) for x in xs]) # B = (P - I) / Z2 b_evaluations = [((p - i) * invq) % modulus for p, i, invq in zip(p_evaluations, i_evaluations, inv_z2_evaluations)] print('Computed B polynomial')
那么，我们的论证如下。证明者想要证明P(1) == input和P(last_step) == output。如果我们将I(x)作为插值，那么就是穿越(1, input)和(last_step, output)亮点的线，于是P(x) – I(x)就会在这亮点上等于零。因此，它会证明P(x) – I(x)是P(x) – I(x)的乘积，并且我们通过提高商数来证明这点。
紫色：计算轨迹多项式 (P) 。绿色：插值 (I)（注意插值是如何构造的，其在 x = 1 处等于输入（应该是计算轨迹的第一步），在 x=g^(steps-1) 处等于输出（应该是计算轨迹的最后一步）。红色：P-I。黄色：在x = 1和 x=g^(steps-1)（即 Z2）处等于 0 的最小多项式。粉红色：(P – I) / Z2。
现在，我们来看看将P，D和B的默克尔根部组合在一起。
现在，我们需要证明P，D和B其实都是多项式，并且是最大的正确阶数。但是FRI证明是很大且昂贵的，而且我们不想有三个FRI证明，所以，我们计算 P，D 和 B 的伪随机线性组合，并且基于它来进行FRI证明：
# Compute their Merkle roots mtree = merkelize([pval.to_bytes(32, 'big') + dval.to_bytes(32, 'big') + bval.to_bytes(32, 'big') for pval, dval, bval in zip(p_evaluations, d_evaluations, b_evaluations)]) print('Computed hash root')
除非所有这三个多项式有正确的低阶，不然几乎不可能有随机选择的线性组合，所以这很足够。
我们想要证明D的阶数小于2 * steps，而且P 和 B 的次数小于steps，所以我们其实使用了随机的P, P * xsteps, B, Bsteps 和 D的随机组合，并且可以看出这部分组合是小于2 * steps。
现在，我们来检查下所有的多项式组合。我们先获得很多随机的索引，然后在这些索引上为默克尔树枝提供多项式：
k1 = int.from_bytes(blake(mtree[1] + b'\x01'), 'big') k2 = int.from_bytes(blake(mtree[1] + b'\x02'), 'big') k3 = int.from_bytes(blake(mtree[1] + b'\x03'), 'big') k4 = int.from_bytes(blake(mtree[1] + b'\x04'), 'big') # Compute the linear combination. We don't even bother calculating it # in coefficient form; we just compute the evaluations root_of_unity_to_the_steps = f.exp(root_of_unity, steps) powers = [1] for i in range(1, precision): powers.append(powers[-1] * root_of_unity_to_the_steps % modulus) l_evaluations = [(d_evaluations[i] + p_evaluations[i] * k1 + p_evaluations[i] * k2 * powers[i] + b_evaluations[i] * k3 + b_evaluations[i] * powers[i] * k4) % modulus for i in range(precision)]
get_pseudorandom_indices函数会回复[0…precision-1]范围中的随机索引，而且exclude_multiples_of参数并不会给出特定参数倍数的值。这就保证了，我们不会沿着原始计算轨迹进行采样，否则就会获得错误的答案。
证明是由一组默克尔根、经过抽查的分支以及随机线性组合的低次证明组成：
# Do some spot checks of the Merkle tree at pseudo-random coordinates, excluding # multiples of `extension_factor` branches = [] samples = spot_check_security_factor positions = get_pseudorandom_indices(l_mtree[1], precision, samples, exclude_multiples_of=extension_factor) for pos in positions: branches.append(mk_branch(mtree, pos)) branches.append(mk_branch(mtree, (pos + skips) % precision)) branches.append(mk_branch(l_mtree, pos)) print('Computed %d spot checks' % samples)
整个证明最长的部分是默克尔树分支，还有FRI证明，这是有更多分支来组成的。这是验证者的实质结果：
o = [mtree[1], l_mtree[1], branches, prove_low_degree(l_evaluations, root_of_unity, steps * 2, modulus, exclude_multiples_of=extension_factor)]
在每个位置，证明者需要提供一个默克尔证明，从而让验证者能够检查这个默克尔证明，并且检查C(P(x), P(g1*x), K(x)) = Z(x) * D(x)以及B(x) * Z2(x) + I(x) = P(x)（提醒：对于不在初始计算轨道上的x，Z(x)不会是零，所以C(P(x), P(g1*x), K(x)也不会是零)。验证者也会检查线性组合是正确的，然后调用。
for i, pos in enumerate(positions): x = f.exp(G2, pos) x_to_the_steps = f.exp(x, steps) mbranch1 = verify_branch(m_root, pos, branches[i*3]) mbranch2 = verify_branch(m_root, (pos+skips)%precision, branches[i*3+1]) l_of_x = verify_branch(l_root, pos, branches[i*3 + 2], output_as_int=True) p_of_x = int.from_bytes(mbranch1[:32], 'big') p_of_g1x = int.from_bytes(mbranch2[:32], 'big') d_of_x = int.from_bytes(mbranch1[32:64], 'big') b_of_x = int.from_bytes(mbranch1[64:], 'big') zvalue = f.div(f.exp(x, steps) - 1, x - last_step_position) k_of_x = f.eval_poly_at(constants_mini_polynomial, f.exp(x, skips2)) # Check transition constraints Q(x) = Z(x) * D(x) assert (p_of_g1x - p_of_x ** 3 - k_of_x - zvalue * d_of_x) % modulus == 0 # Check boundary constraints B(x) * Z2(x) + I(x) = P(x) interpolant = f.lagrange_interp_2([1, last_step_position], [inp, output]) zeropoly2 = f.mul_polys([-1, 1], [-last_step_position, 1]) assert (p_of_x - b_of_x * f.eval_poly_at(zeropoly2, x) - f.eval_poly_at(interpolant, x)) % modulus == 0 # Check correctness of the linear combination assert (l_of_x - d_of_x - k1 * p_of_x - k2 * p_of_x * x_to_the_steps - k3 * b_of_x - k4 * b_of_x * x_to_the_steps) % modulus == 0
其实还没有完成成功；证明对跨多项式检查和 FRI 所需的抽查次数的可靠性分析是非常棘手的。但是这些就是所有代码，至少你不用担心进行疯狂的优化。当我运行以上代码的时候，我们会获得STARK证明，会有300-400倍的证明成本例如，一个需要 0.2 秒的 MIMC 计算需要 60 秒来证明）。这就使得4核机器计算MIMC中的 STARK，实际上可以比后向计算 MIMC 更快。也就是说，在python语言，这会相对低效的实现，并且这也会证明运行时间比例会不同。同时，也值得指出，MIMC 的 STARK 证明成本非常低，因为MIMC几乎是完美地可计算，它的数学形式很简单。对于平均计算，会包含更少的清晰计算（例如，检查一个数是大于还是小于另一个），其计算成本可能会更高，会有大约10000-50000倍。
opencv常用函数
原文链接：
1、cvLoadImage：将图像文件加载至内存；
2、cvNamedWindow：在屏幕上创建一个窗口；
3、cvShowImage：在一个已创建好的窗口中显示图像；
4、cvWaitKey：使程序暂停，等待用户触发一个按键操作；
5、cvReleaseImage：释放图像文件所分配的内存；
6、cvDestroyWindow：销毁显示图像文件的窗口；
7、cvCreateFileCapture：通过参数设置确定要读入的AVI文件；
8、cvQueryFrame：用来将下一帧视频文件载入内存；
9、cvReleaseCapture：释放CvCapture结构开辟的内存空间；
10、cvCreateTrackbar：创建一个滚动条；
11、cvSetCaptureProperty：设置CvCapture对象的各种属性；
12、cvGetCaptureProperty：查询CvCapture对象的各种属性；
13、cvGetSize：当前图像结构的大小；
14、cvSmooth：对图像进行平滑处理；
15、cvPyrDown：图像金字塔，降采样，图像缩小为原来四分之一；
16、cvCanny：Canny边缘检测；
17、cvCreateCameraCapture：从摄像设备中读入数据；
18、cvCreateVideoWriter：创建一个写入设备以便逐帧将视频流写入视频文件；
19、cvWriteFrame：逐帧将视频流写入文件；
20、cvReleaseVideoWriter：释放CvVideoWriter结构开辟的内存空间；
21、CV_MAT_ELEM：从矩阵中得到一个元素；
22、cvAbs：计算数组中所有元素的绝对值；
23、cvAbsDiff：计算两个数组差值的绝对值；
24、cvAbsDiffS：计算数组和标量差值的绝对值；
25、cvAdd：两个数组的元素级的加运算；
26、cvAddS：一个数组和一个标量的元素级的相加运算；
27、cvAddWeighted：两个数组的元素级的加权相加运算(alpha运算)；
28、cvAvg：计算数组中所有元素的平均值；
29、cvAvgSdv：计算数组中所有元素的绝对值和标准差；
30、cvCalcCovarMatrix：计算一组n维空间向量的协方差；
31、cvCmp：对两个数组中的所有元素运用设置的比较操作；
32、cvCmpS：对数组和标量运用设置的比较操作；
33、cvConvertScale：用可选的缩放值转换数组元素类型；
34、cvCopy：把数组中的值复制到另一个数组中；
35、cvCountNonZero：计算数组中非0值的个数；
36、cvCrossProduct：计算两个三维向量的向量积(叉积)；
37、cvCvtColor：将数组的通道从一个颜色空间转换另外一个颜色空间；
38、cvDet：计算方阵的行列式；
39、cvDiv：用另外一个数组对一个数组进行元素级的除法运算；
40、cvDotProduct：计算两个向量的点积；
41、cvEigenVV：计算方阵的特征值和特征向量；
42、cvFlip：围绕选定轴翻转；
43、cvGEMM：矩阵乘法；
44、cvGetCol：从一个数组的列中复制元素；
45、cvGetCols：从数据的相邻的多列中复制元素；
46、cvGetDiag：复制数组中对角线上的所有元素；
47、cvGetDims：返回数组的维数；
48、cvGetDimSize：返回一个数组的所有维的大小；
49、cvGetRow：从一个数组的行中复制元素值；
50、cvGetRows：从一个数组的多个相邻的行中复制元素值；
51、cvGetSize：得到二维的数组的尺寸，以CvSize返回；
52、cvGetSubRect：从一个数组的子区域复制元素值；
53、cvInRange：检查一个数组的元素是否在另外两个数组中的值的范围内；
54、cvInRangeS：检查一个数组的元素的值是否在另外两个标量的范围内；
55、cvInvert：求矩阵的逆；
56、cvMahalonobis：计算两个向量间的马氏距离；
57、cvMax：在两个数组中进行元素级的取最大值操作；
58、cvMaxS：在一个数组和一个标量中进行元素级的取最大值操作；
59、cvMerge：把几个单通道图像合并为一个多通道图像；
60、cvMin：在两个数组中进行元素级的取最小值操作；
61、cvMinS：在一个数组和一个标量中进行元素级的取最小值操作；
62、cvMinMaxLoc：寻找数组中的最大最小值；
63、cvMul：计算两个数组的元素级的乘积(点乘)；
64、cvNot：按位对数组中的每一个元素求反；
65、cvNormalize：将数组中元素进行归一化；
66、cvOr：对两个数组进行按位或操作；
67、cvOrs：在数组与标量之间进行按位或操作；
68、cvReduce：通过给定的操作符将二维数组简为向量；
69、cvRepeat：以平铺的方式进行数组复制；
70、cvSet：用给定值初始化数组；
71、cvSetZero：将数组中所有元素初始化为0；
72、cvSetIdentity：将数组中对角线上的元素设为1，其他置0；
73、cvSolve：求出线性方程组的解；
74、cvSplit：将多通道数组分割成多个单通道数组；
75、cvSub：两个数组元素级的相减；
76、cvSubS：元素级的从数组中减去标量；
77、cvSubRS：元素级的从标量中减去数组；
78、cvSum：对数组中的所有元素求和；
79、cvSVD：二维矩阵的奇异值分解；
80、cvSVBkSb：奇异值回代计算；
81、cvTrace：计算矩阵迹；
82、cvTranspose：矩阵的转置运算；
83、cvXor：对两个数组进行按位异或操作；
84、cvXorS：在数组和标量之间进行按位异或操作；
85、cvZero：将所有数组中的元素置为0；
86、cvConvertScaleAbs：计算可选的缩放值的绝对值之后再转换数组元素的类型；
87、cvNorm：计算数组的绝对范数， 绝对差分范数或者相对差分范数；
88、cvAnd：对两个数组进行按位与操作；
89、cvAndS：在数组和标量之间进行按位与操作；
90、cvScale：是cvConvertScale的一个宏，可以用来重新调整数组的内容，并且可以将参数从一种数据类型转换为另一种；
91、cvT：是函数cvTranspose的缩写；
92、cvLine：画直线；
93、cvRectangle：画矩形；
94、cvCircle：画圆；
95、cvEllipse：画椭圆；
96、cvEllipseBox：使用外接矩形描述椭圆；
97、cvFillPoly、cvFillConvexPoly、cvPolyLine：画多边形；
98、cvPutText：在图像上输出一些文本；
99、cvInitFont：采用一组参数配置一些用于屏幕输出的基本个特定字体；
100、cvSave：矩阵保存；
101、cvLoad：矩阵读取；
102、cvOpenFileStorage：为读/写打开存储文件；
103、cvReleaseFileStorage：释放存储的数据；
104、cvStartWriteStruct：开始写入新的数据结构；
105、cvEndWriteStruct：结束写入数据结构；
106、cvWriteInt：写入整数型；
107、cvWriteReal：写入浮点型；
108、cvWriteString：写入字符型；
109、cvWriteComment：写一个XML或YAML的注释字串；
110、cvWrite：写一个对象；
111、cvWriteRawData：写入多个数值；
112、cvWriteFileNode：将文件节点写入另一个文件存储器；
113、cvGetRootFileNode：获取存储器最顶层的节点；
114、cvGetFileNodeByName：在映图或存储器中找到相应节点；
115、cvGetHashedKey：为名称返回一个惟一的指针；
116、cvGetFileNode：在映图或文件存储器中找到节点；
117、cvGetFileNodeName：返回文件的节点名；
118、cvReadInt：读取一个无名称的整数型；
119、cvReadIntByName：读取一个有名称的整数型；
120、cvReadReal：读取一个无名称的浮点型；
121、cvReadRealByName：读取一个有名称的浮点型；
122、cvReadString：从文件节点中寻找字符串；
123、cvReadStringByName：找到一个有名称的文件节点并返回它；
124、cvRead：将对象解码并返回它的指针；
125、cvReadByName：找到对象并解码；
126、cvReadRawData：读取多个数值；
127、cvStartReadRawData：初始化文件节点序列的读取；
128、cvReadRawDataSlice：读取文件节点的内容；
129、cvGetModuleInfo：检查IPP库是否已经正常安装并且检验运行是否正常；
130、cvResizeWindow：用来调整窗口的大小；
131、cvSaveImage：保存图像；
132、cvMoveWindow：将窗口移动到其左上角为x,y的位置；
133、cvDestroyAllWindow：用来关闭所有窗口并释放窗口相关的内存空间；
134、cvGetTrackbarPos：读取滑动条的值；
135、cvSetTrackbarPos：设置滑动条的值；
136、cvGrabFrame：用于快速将视频帧读入内存；
137、cvRetrieveFrame：对读入帧做所有必须的处理；
138、cvConvertImage：用于在常用的不同图像格式之间转换；
139、cvErode：形态腐蚀；
140、cvDilate：形态学膨胀；
141、cvMorphologyEx：更通用的形态学函数；
142、cvFloodFill：漫水填充算法，用来进一步控制哪些区域将被填充颜色；
143、cvResize：放大或缩小图像；
144、cvPyrUp：图像金字塔，将现有的图像在每个维度上都放大两倍；
145、cvPyrSegmentation：利用金字塔实现图像分割；
146、cvThreshold：图像阈值化；
147、cvAcc：可以将8位整数类型图像累加为浮点图像；
148、cvAdaptiveThreshold：图像自适应阈值；
149、cvFilter2D：图像卷积；
150、cvCopyMakeBorder：将特定的图像轻微变大，然后以各种方式自动填充图像边界；
151、cvSobel：图像边缘检测，Sobel算子；
152、cvLaplace：拉普拉斯变换、图像边缘检测；
153、cvHoughLines2：霍夫直线变换；
154、cvHoughCircles：霍夫圆变换；
155、cvRemap：图像重映射，校正标定图像，图像插值；
156、cvWarpAffine：稠密仿射变换；
157、cvGetQuadrangleSubPix：仿射变换；
158、cvGetAffineTransform：仿射映射矩阵的计算；
159、cvCloneImage：将整个IplImage结构复制到新的IplImage中；
160、cv2DRotationMatrix：仿射映射矩阵的计算；
161、cvTransform：稀疏仿射变换；
162、cvWarpPerspective：密集透视变换(单应性)；
163、cvGetPerspectiveTransform：计算透视映射矩阵；
164、cvPerspectiveTransform：稀疏透视变换；
165、cvCartToPolar：将数值从笛卡尔空间到极坐标(极性空间)进行映射；
166、cvPolarToCart：将数值从极性空间到笛卡尔空间进行映射；
167、cvLogPolar：对数极坐标变换；
168、cvDFT：离散傅里叶变换；
169、cvMulSpectrums：频谱乘法；
170、cvDCT：离散余弦变换；
171、cvIntegral：计算积分图像；
172、cvDistTransform：图像的距离变换；
173、cvEqualizeHist：直方图均衡化；
174、cvCreateHist：创建一新直方图；
175、cvMakeHistHeaderForArray：根据已给出的数据创建直方图；
176、cvNormalizeHist：归一化直方图；
177、cvThreshHist：直方图阈值函数；
178、cvCalcHist：从图像中自动计算直方图；
179、cvCompareHist：用于对比两个直方图的相似度；
180、cvCalcEMD2：陆地移动距离(EMD)算法；
181、cvCalcBackProject：反向投影；
182、cvCalcBackProjectPatch：图块的方向投影；
183、cvMatchTemplate：模板匹配；
184、cvCreateMemStorage：用于创建一个内存存储器；
185、cvCreateSeq：创建序列；
186、cvSeqInvert：将序列进行逆序操作；
187、cvCvtSeqToArray：复制序列的全部或部分到一个连续内存数组中；
188、cvFindContours：从二值图像中寻找轮廓；
189、cvDrawContours：绘制轮廓；
190、cvApproxPoly：使用多边形逼近一个轮廓；
191、cvContourPerimeter：轮廓长度；
192、cvContoursMoments：计算轮廓矩；
193、cvMoments：计算Hu不变矩；
194、cvMatchShapes：使用矩进行匹配；
195、cvInitLineIterator：对任意直线上的像素进行采样；
196、cvSampleLine：对直线采样；
197、cvAbsDiff：帧差；
198、cvWatershed：分水岭算法；
199、cvInpaint：修补图像；
200、cvGoodFeaturesToTrack：寻找角点；
201、cvFindCornerSubPix：用于发现亚像素精度的角点位置；
202、cvCalcOpticalFlowLK：实现非金字塔的Lucas-Kanade稠密光流算法；
203、cvMeanShift：mean-shift跟踪算法；
204、cvCamShift：camshift跟踪算法；
205、cvCreateKalman：创建Kalman滤波器；
206、cvCreateConDensation：创建condensation滤波器；
207、cvConvertPointsHomogenious：对齐次坐标进行转换；
208、cvFindChessboardCorners：定位棋盘角点；
209、cvFindHomography：计算单应性矩阵；
210、cvRodrigues2：罗德里格斯变换；
211、cvFitLine：直线拟合算法；
212、cvCalcCovarMatrix：计算协方差矩阵；
213、cvInvert：计算协方差矩阵的逆矩阵；
214、cvMahalanobis：计算Mahalanobis距离；
215、cvKMeans2：K均值；
216、cvCloneMat：根据一个已有的矩阵创建一个新矩阵；
217、cvPreCornerDetect：计算用于角点检测的特征图；
218、cvGetImage：CvMat图像数据格式转换成IplImage图像数据格式；
219、cvMatMul：两矩阵相乘；
MMsegmentation教程 6: 自定义运行设定
我们已经支持 PyTorch 自带的所有优化器，唯一需要修改的地方是在配置文件里的 optimizer 域里面。
例如，如果您想使用 ADAM (注意如下操作可能会让模型表现下降)，可以使用如下修改：
为了修改模型的学习率，使用者仅需要修改配置文件里 optimizer 的 lr 即可。
使用者可以参照 PyTorch 的 API 文档
直接设置参数。
一个自定义的优化器可以按照如下去定义：
假如您想增加一个叫做 MyOptimizer 的优化器，它的参数分别有 a , b , 和 c 。
您需要创建一个叫 mmseg/core/optimizer 的新文件夹。
然后再在文件，即 mmseg/core/optimizer/my_optimizer.py 里面去实现这个新优化器：
为了让上述定义的模块被框架发现，首先这个模块应该被导入到主命名空间 (main namespace) 里。
有两种方式可以实现它。
mmseg.core.optimizer.my_optimizer 模块将会在程序运行的开始被导入，并且 MyOptimizer 类将会自动注册。
需要注意只有包含 MyOptimizer 类的包 (package) 应当被导入。
而 mmseg.core.optimizer.my_optimizer.MyOptimizer 不能 被直接导入。
事实上，使用者完全可以用另一个按这样导入方法的文件夹结构，只要模块的根路径已经被添加到 PYTHONPATH 里面。
之后您可以在配置文件的 optimizer 域里面使用 MyOptimizer
在配置文件里，优化器被定义在 optimizer 域里，如下所示：
为了使用您自己的优化器，这个域可以被改成：
有些模型可能需要在优化器里有一些特别参数的设置，例如 批归一化层 (BatchNorm layers) 的 权重衰减 (weight decay)。
使用者可以通过自定义优化器的构造器去微调这些细粒度参数。
默认的优化器构造器的实现可以参照 这里 ，它也可以被用作新的优化器构造器的模板。
优化器没有实现的一些技巧应该通过优化器构造器 (optimizer constructor) 或者钩子 (hook) 去实现，如设置基于参数的学习率 (parameter-wise learning rates)。我们列出一些常见的设置，它们可以稳定或加速模型的训练。
如果您有更多的设置，欢迎在 PR 和 issue 里面提交。
我们根据默认的训练迭代步数 40k/80k 来设置学习率，这在 MMCV 里叫做 PolyLrUpdaterHook 。
我们也支持许多其他的学习率计划表： 这里 ，例如 CosineAnnealing 和 Poly 计划表。下面是一些例子：
工作流是一个专门定义运行顺序和轮数 (running order and epochs) 的列表 (phase, epochs)。
默认情况下它设置成：
意思是训练是跑 1 个 epoch。有时候使用者可能想检查模型在验证集上的一些指标（如 损失 loss，精确性 accuracy），我们可以这样设置工作流：
于是 1 个 epoch 训练，1 个 epoch 验证将交替运行。
注意 :
如果钩子已经在 MMCV 里被实现，如下所示，您可以直接修改配置文件来使用钩子：
以下的常用的钩子没有被 custom_hooks 注册：
在这些钩子里，只有 logger hook 有 VERY_LOW 优先级，其他的优先级都是 NORMAL 。
上述提及的教程已经包括了如何修改 optimizer_config ， momentum_config 和 lr_config 。
这里我们展示我们如何处理 log_config ， checkpoint_config 和 evaluation 。
MMCV runner 将使用 checkpoint_config 去初始化 CheckpointHook .
使用者可以设置 max_keep_ckpts 来仅保存一小部分检查点或者通过 save_optimizer 来决定是否保存优化器的状态字典 (state dict of optimizer)。 更多使用参数的细节请参考 这里 。
log_config 包裹了许多日志钩 (logger hooks) 而且能去设置间隔 (intervals)。现在 MMCV 支持 WandbLoggerHook ， MlflowLoggerHook 和 TensorboardLoggerHook 。
详细的使用请参照 文档 。
evaluation 的配置文件将被用来初始化 EvalHook 。
除了 interval 键，其他的像 metric 这样的参数将被传递给 dataset.evaluate() 。
关注微信公众号
