# B-spline

In the mathematical subfield of numerical analysis, a B-spline is a spline function that has minimal support with respect to a given degree, smoothness, and domain partition. A fundamental theorem states that every spline function of a given degree, smoothness and domain partition, can be represented as a linear combination of B-splines of that same degree and smoothness, and over that same partition. The term B-spline was coined by Isaac Jacob Schoenberg and is short for basis spline. B-splines can be evaluated in a numerically stable way by the de Boor algorithm.

In the computer science subfields of computer-aided design and computer graphics the term B-spline frequently refers to a spline curve parametrized by spline functions that are expressed as linear combinations of B-splines (in the mathematical sense above). A B-spline is simply a generalisation of a Bézier curve, and it can avoid the Runge phenomenon without increasing the degree of the B-spline.

[hide]

## Definition

Given m+1 knots with

a B-spline of degree n is a parametric curve

composed of basis B-splines of degree n

.

The Pi are called control points or de Boor points. (There are m-n control points.) A polygon can be constructed by connecting the de Boor points with lines, starting with P0 and finishing with Pm-n-1. This polygon is called the de Boor polygon.

The m-n basis B-splines of degree n can be defined using the Cox-de Boor recursion formula

When the knots are equidistant we say the B-spline is uniform otherwise we call it non-uniform. If two knots tj are identical, we deem .

### Uniform B-spline

When the B-spline is uniform, the basis B-splines for a given degree n are just shifted copies of each other. An alternative non-recursive definition for the m-n basis B-splines is

with

and

where

is the truncated power function.

## Notes

When the number of knots is the same as the degree, the B-Spline degenerates into a Bézier curve. The shape of the basis functions is determined by the position of the knots. Scaling or translating the knot vector does not alter the basis functions.

The spline is contained in the convex hull of its control points.

A basis B-spline of degree n

is non-zero only in the interval [ti, ti+n+1] that is

In other words if we manipulate one control point we only change the local behaviour of the curve and not the global behaviour as with Bézier curves.

The basis function can be derived from the Bernstein polynomial.

## Examples

### Constant B-spline

The constant B-spline is the most simple spline. It is defined on only one knot span and is not even continuous on the knots. It is a just indicator function for the different knot spans.

### Linear B-spline

The linear B-spline is defined on two consecutive knot spans and is continuous on the knots, but not differentiable.

Quadratic B-splines with uniform knot-vector is a commonly used form of B-spline. The blending function can easily be precalculated, and is equal for each segment in this case.

Put in matrix-form, it is:

for
• Reference .

### Cubic B-Spline

A B-spline formulation for a single segment can be written as:

where Si is the ith B-spline segment and P is the set of control points, segment i and k is the local control point index. A set of control points would be where the wi is weight, pulling the curve towards control point Pi as it increases or moving the curve away as it decreases.

An entire set of segments, m-2 curves (S3,S4,...,Sm) defined by m+1 control points (), as one B-spline in t would be defined as:

where i is the control point number and t is a global parameter giving knot values. This formulation expresses a B-spline curve as a linear combination of B-spline basis functions, hence the name.

There are two types of B-spline - uniform and non-uniform. A non-uniform B-spline is a curve where the intervals between successive control points is not, or not necessarily, equal (the knot vector of interior knot spans are not equal). A common form is where intervals are successively reduced to zero, interpolating control points.

### Uniform cubic B-splines

Cubic B-splines with uniform knot-vector is the most commonly used form of B-spline. The blending function can easily be precalculated, and is equal for each segment in this case. Put in matrix-form, it is:

for

## References

1. ^ Carl de Boor (1978). A Practical Guide to Splines. Springer-Verlag, 113-114.
2. ^ Carl de Boor (1978). A Practical Guide to Splines. Springer-Verlag, 114-115.

#### '알고리즘 > 이미지 처리' 카테고리의 다른 글

 Bicubic interpolation  (0) 2008.03.09 2008.03.07 2008.03.06 2008.03.06 2008.03.05 2008.03.05
자료검색 빡세네...

#### '알고리즘 > 이미지 처리' 카테고리의 다른 글

 이미지 분활 와핑에 관해서.  (0) 2008.03.07 2008.03.06 2008.03.06 2008.03.05 2008.03.05 2008.03.05 #include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

// 피보팅을 처리하는 함수 구현
void pivoting(double **matrix, int currentRow, int currentCol, int rowSize, int colSize){
double *temp;
temp =  new double[colSize];

double max = fabs(matrix[currentRow][currentCol]); // 우선 현재행,현재열 값을 최대값으로 지정

for(int i=currentRow+1; i<rowSize; i++){
if(fabs(matrix[i][currentCol]) > max){
temp = matrix[currentRow];
matrix[currentRow] = matrix[i];
matrix[i] = temp;
max = matrix[currentRow][currentCol];
}
}
}

// 임의 크기의 행렬의 가우시안소거법 함수 구현
void gaussianElimination(double **matrix, int rowSize, int colSize){
double temp;
int i,j,k;

pivoting(matrix,0,0,rowSize,colSize);

for(i=0; i<rowSize-1; i++){
for(j=i+1; j<rowSize; j++){

pivoting(matrix,i,i,rowSize,colSize);

temp = matrix[j][i] / matrix[i][i];
for(k=0; k<colSize; k++){
matrix[j][k] = matrix[j][k] - matrix[i][k]*temp;
}
}
}

}

// 역행렬이 존재하는지 확인하는 함수 구현
int existINV(double **matrix, int size){
double temp = 1.0;
gaussianElimination(matrix, size, 2*size);
for(int i=0; i<size; i++){ // 가우시안 소거법으로 상삼각 행렬을 만든후 대각요소의 곱을 구함
temp *= matrix[i][i];
}
if(temp != 0) // 대각곱이 0이 아니면 역행렬이 존재하고 0이면 역행렬이 존재하지 않는다
return 1;
else
return 0;
}

// 역행렬을 구하는 함수 구현
void solveInverse(double **matrix, int size, double **inv){
for(int i=0; i<size; i++){ // 열의 인덱스
inv[size-1][i] = matrix[size-1][size+i] / matrix[size-1][size-1];
for(int j=size-2; j>=0; j--){
double temp = 0.0;
for(int k=size-1; k>j; k--){
temp += (matrix[j][k]*inv[k][i]);
}
inv[j][i] = (matrix[j][size+i]-temp) / matrix[j][j];
}
}
}

// n x n 크기의 행렬을 저장하기 위한 함수 구현
void enter_nxn_Matrix(double **matrix, int size){
for(int i=0; i<size; i++){
cout << i+1 << "행의 값들을 넣어주세요 (예) 2 4 5 3 ... -> ";
for(int j=0; j<size; j++){
cin >> matrix[i][j];
}
}
for(i=0; i<size; i++){
for(int j=size; j<2*size; j++){
if((i+size) == j)
matrix[i][j] = 1;
else
matrix[i][j] = 0;
}
}
}

// 임의 크기의 행렬을 출력하는 함수 구현
void showMatrix(double **matrix, int rowSize, int colSize){
cout << endl << "< 입력하신 행렬의 역행렬은 다음과 같습니다 >" << endl;
for(int i=0; i<rowSize; i++){
cout << endl;

if(i==0) cout << "┏";
else if(i==rowSize-1) cout << "┗";
else cout << "┃";

for(int j=0; j<colSize; j++){
cout << setw(12) << matrix[i][j];
}

if(i==0) cout << " ┓";
else if(i==rowSize-1) cout << " ┛";
else cout << " ┃";
}
cout << endl << endl;
}

int main(){
double **matrix, **inv;
int size;

cout << "n by n 행렬의 크기 n 값을 넣어주세요 (예) 5 -> ";
cin >> size;

matrix = new double*[size];
inv = new double*[size];
for(int i=0; i < size; i++){
matrix[i] = new double [size*2];
inv[i] = new double [size];
}

enter_nxn_Matrix(matrix, size);
//showMatrix(matrix, size, size);
if(!existINV(matrix, size)){
cout << endl << "< 역행렬이 존재하지 않는 행렬이므로 프로그램을 종료합니다 >" << endl;
return 0;
}
//showMatrix(matrix, size, 2*size);
solveInverse(matrix,size,inv);
showMatrix(inv, size, size);
return 1;
}

#### '알고리즘 > 이미지 처리' 카테고리의 다른 글

 Cubic B-Splines from wikipeda ...  (0) 2008.03.06 2008.03.06 2008.03.05 2008.03.05 2008.03.05 2008.03.04

# 위키백과 ― 우리 모두의 백과사전.

이중선형 필터링(Bilinear filtering)은 컴퓨터 그래픽스에서 실제 크기보다 크거나 작게 표시되는 텍스쳐보간하는데 쓰는 방식이다.

텍스쳐를 씌운 도형을 화면에 그릴 때, 대부분의 경우는 텍스쳐가 왜곡 없이 저장된 정보 그대로 화면에 표시되지는 않는다. 하지만, 텍스쳐를 확대 축소시키거나 보는 시점을 바꾸면 텍스쳐 상의 픽셀(텍셀)이 튀어 보이게 된다. 이선형 필터링은 텍스쳐상의 임의의 텍셀과 그와 4방향으로 인접한 텍셀들의 중점에 대하여 선형 보간법을 수행하여 텍스쳐가 어떤 경우에라도 부드럽게 보일 수 있도록 한다.

## [편집]공식

다음 방정식에서 uk와 vk는 텍스쳐의 좌표이며, yk는 점 k의 색을 나타낸다. 첨자가 없는 값은 픽셀의 점을 나타내며, 첨자 0, 1, 2, 3을 가지는 값은 각각 픽셀과 인접해 있는 상, 좌, 우, 하의 텍셀을 나타낸다. 다음 이원일차 방정식은 선형 보간법 공식이다.

텍스쳐가 정사각형 비트맵이라고 가정하면 $v_1 = v_0 \,\!$ $v_2 = v_3 \,\!$ $u_1 = u_3 \,\!$ $u_2 = u_0 \,\!$ $v_3 - v_0 = u_3 - u_0 = w \,\!$

이 식이 모두 참이 된다. 나아가서 다음 식을 정의하면 $U = \frac{u - u_0}{w} \,\!$ $V = \frac{v - v_0}{w} \,\!$

이렇게 해서 보간법 방정식을 단순화시킬수 있다: $y_a = y_0 + (y_1-y_0)U \,\!$ $y_b = y_2 + (y_3-y_2)U \,\!$ $y = y_a + (y_b-y_a)V \,\!$

위의 식을 결합시키면 다음과 같다: $y = y_0 + (y_1 - y_0)U + (y_2 - y_0)V + (y_3 - y_2 - y_1 + y_0)UV \,\!$

다르게 표현하면: $y = y_0(1 - U)(1 - V) + y_1 U (1 - V) + y_2 (1 - U) V + y_3 U V \,\!$

이 된다.

하지만, 이미지가 회전, 전단 이동 또는 시점 변환되는것이 아니라 단지 확대 및 축소만 할 경우에는, 따로 방정식을 만들고 yb (크기를 키울 경우에는 때때로 ya)를 다음 행에서 사용할 수 있도록 보관한다면 비교적 속도 향상을 꾀할 수 있다.

#### '알고리즘 > 이미지 처리' 카테고리의 다른 글

 B-Spline을 활용하는 이미지 와핑 관련...  (0) 2008.03.06 2008.03.05 2008.03.05 2008.03.05 2008.03.04 2008.02.26