[CE] Subdivision using DFS

이 페이지는 Recursive subdivision의 동작을 간단한 binary image를 대상으로 보여준다.

 

사용한 image는 The Secret Life of Programs 의 5장에 나오는 Figure 5-3: A crude simley face를 사용하면서 단지 좌표를 일반적인 image에서 사용하는대로 top-left pixel을 0,0으로 처리했다.

 

최종으로 나오는 Tree의 leaf node의 갯수는 40개로 원래의 64개보다 줄어들며, 일종의 압축된 representation을 형성한다.

 

Pseudo code 및 동작

이 Recursive subdivision 예제의 Pseudo code (Recursive Functon이 사용됨)는 다음과 같다.

function subdivide(x, y, size)
{
    IF size != 1 AND "the pixels in the square are not all the same color" {
        half = size / 2
        subdivide(x, y, half)                # upper left quadrant
        subdivide(x, y + half, half)         # lower left quadrant
        subdivide(x + half, y + half, half)  # lower right quadrant
        subdivide(x + half, y, half)         # upper right quadrant                        
    }
    ELSE {
        save the information about the square
    }
}

동작은 다음과 같음.

위의 image subdivision은 Depth-First-Search로 동작하며, stack과 recursive call을 통해 쉽게 구현할 수 있음.

Stack

Stack과 stack frame은 다음과 같음.

• recursive call이 발생할 때마다, 귀환할 주소와 해당 call의 parameter에 할당된 argument를 stack에 집어넣음.

Stack Frame : stack에 저장된 데이터들의 모음 을 Stack Frame이라고 부르고 다음으로 구성됨.

• function(=subroutine)으로 전달하는 parameters (이들의 값은 호출 시 사용된 argument임)
• local variables (C언어)
• 복귀 주소

---

다음 url들을 같이 보면 도움이 됨.

2023.05.23 - [Computer/CE] - [CE] Stack

[CE] Stack

2023.05.24 - [Programming] - [Python] recursive call : Fibonacci Sequence

[Python] recursive call : Fibonacci Sequence

 

2023.02.20 - [Computer/CE] - [CE] Tree vs. Graph

[CE] Tree vs. Graph

https://nostarch.com/foundationsofcomp

The Secret Life of Programs