1. 그레이스케일

이건 이미지를 흑백 형태로 바꾸는 것이 핵심이다. 색을 구성하는 정보량의 차원이 줄어들고(3차원 → 1차원으로) 결과적으로 전체 색깔수가 줄어들기는 하지만(수천~수십만 종류의 색상 → 256단계의 회색), 그래도 아예 B&W 단색으로 바꾸는 건 아니다.
각 픽셀들은 색상과 채도가 제거되고 명도만 남아서 흑부터 백 사이에 다양한 명도의 회색으로 기계적으로 바뀐다. 같은 색의 픽셀이 인접 픽셀이 무엇이냐에 따라서 다르게 바뀐다거나 하지는 않는다.

그런데 그레이스케일 공식이 딱 하나만 존재하는 게 아니다. RGB 세 성분의 산술평균을 주면 될 것 같지만, 그렇게 그레이스케일을 하면 그림이 굉장히 칙칙하고 탁하게 보이게 된다.

똑같이 최대값 255를 주더라도 빨강(255,0,0), 초록(0,255,0), 파랑(0,0,255) 각 색별로 사람이 인지하는 명도는 서로 일치하지 않는다. VGA 16색 팔레트를 다뤄 본 사람이라면, 밝은 빨강이나 밝은 파랑을 바탕으로는 흰 글자가 어울리지만, 밝은 초록은 그 자체가 너무 밝아서 흰 글자가 어울리지 않는다는 것을 알 것이다.

사용자 삽입 이미지

그러니 공평하게 33, 33, 33씩 가중치를 주는 게 아니라 거의 30, 60, 10에 가깝게.. 초록에 가중치를 제일 많이 부여하고 파랑에는 가중치를 아주 짜게 주는 것이 자연스럽다고 한다.

이런 공식은 누가 언제 고안했으며 무슨 물리 상수처럼 측정 가능한 과학적인 근거가 있는지 궁금하다. 옛날에 흑백 사진을 찍으면 색깔이 딱 저 공식에 근거한 밝기의 grayscale로 바뀌었던가?
본인은 저 그레이스케일 공식을 태어나서 처음으로 접한 곳이 아마 QBasic 내지 QuickBasic의 컬러/팔레트 관련 명령어의 도움말이었지 싶다.

2. 디더링

이건 그레이스케일과 달리, 색깔수를 확 줄이는 것이 핵심이다. 그 대신 반드시 단색 흑백이어야 할 필요가 없다. 가령, 트루컬러를 16색으로 줄이는 것이라면 RGB 원색이 살아 있는 컬러라 할지라도 디더링의 범주에 든다. 이런 것처럼 말이다.

사용자 삽입 이미지

디더링에서는 어떤 원색을 직통으로 표현할 수 없을 때 근처의 비슷한 여러 색들을 고르게 흩뿌려서 원색과 비슷한 색감을 나타낸다. 팔레트까지 임의로 지정이 가능하다면 256색 정도만 돼도 생각보다 그럴싸하게 원래 이미지를 재현할 수 있다. 그런 게 아니라 그냥 흑백 단색 디더링이라면 아까 그레이스케일처럼 어떤 공식에 근거해서 명도를 추출할지를 먼저 결정해야 할 것이다.

0부터 1까지 가중치별로 점을 골고루 균등하게 뿌리는 공식은 이미 다 만들어져 있다. 이건 Ordered dither이라고 불리며, 보통 8*8 크기의 64단계 격자가 쓰이는 편이다. 그 구체적인 방식에 대해서는 수 년 전에 이 블로그에서 이미 다룬 적이 있다.

그레이스케일은 RGB(0.4,0.2,0.6)라는 색을 0.3이라는 명도로 바꾸는 것에 해당하는 기술이고, 단색 디더링은 이 색이 0.3, 0.3, 0.3 … 이렇게 쭉 이어지는 것을 1, 0, 0, 1, 0, 0 이런 식으로 이산적으로 표현하는 것과 같다.
그런데 원색을 기계적으로 이런 격자로 치환하기만 하면 보기가 생각보다 굉장히 좋지 않다.

원래 0.3을 표현해야 하는데 지금 지점에서 부득이하게 1을 찍어 버렸다면 0.7이라는 오차의 여파를 인접 픽셀에다가 떠넘겨서 거기서 계속해서 감당하게 해야 한다. 즉, 그레이스케일은 그냥 인접 픽셀을 신경 쓰지 않고 픽셀 대 픽셀 변환만 했지만 디더링은 그렇지 않다. ordered dither 내지 더 단순무식한 nearest color 찍기 신공이 아니라면.. 이전 픽셀에서 발생한 오차를 수습하는 error diffusion을 동원해야 부드러운 결과물이 나온다.

사용자 삽입 이미지

그런 지능적인(?) 디더링 알고리즘은 196~70년대에 컴퓨터그래픽이라는 분야가 등장한 초창기부터 연구되어 왔으며, 고안자의 이름을 따서 Floyd-Steinberg, Burks, Stucki 같은 알고리즘이 있다. 이미지를 다루는 사람이라면 포토샵 같은 그래픽 편집 프로그램에서 저런 명칭들을 본 적이 있을 것이다.
이런 알고리즘들은 ordered dither와 달리, 점들이 일정 간격으로 산술· 기계적으로 단순 투박하게 찍힌 게 아니라 뭔가 한땀 한땀 손으로 입력된 것 같고 부드러운 느낌이 든다. 그리고 무엇보다 색깔이 크게 바뀌는 경계 영역이 훨씬 더 선명하다.

3. 하프톤 (망점)

그레이스케일이 색깔 표현에 제약이 없는 아날로그 영상물(특히 흑백 필름 사진) 같은 느낌이 나고, 디더링은 초기에 해상도와 색상이 부족했던 디지털 영상과 관계가 있다면.. 하프톤은 색상이 부족한 대신 해상도가 높은 '인쇄물'과 관계가 깊은 기법이다.

사용자 삽입 이미지

하프톤은.. 일정 간격으로 망점을 두두두둑.. 찍고, 그 망점의 크기/굵기만으로 명도를 조절한다. 깨알같은 점들의 양과 배치 방식을 고민하는 통상적인 디더링과는 문제 접근 방식이 약간 다르다.
출력물의 해상도가 영 시원찮은 데서 하프톤을 동원하면 망점이 너무 커서 눈에 거슬릴 수 있다. 회색을 만들려고 했는데 하양과 검정이 그대로 눈에 띄게 된다는 것이다.

그러나 아무 인쇄물에서나 흑백이든 컬러든 문자 말고 음영(색깔 배경)이나 사진을 하나 보시기 바란다. 전부 촘촘한 점들로 구성돼 있다.
컴퓨터용 프린터나 전문 출판물 인쇄기들이 무슨 수십~수백 종에 달하는 물감을 갖고 있지는 않다. 잉크는 3원색에다가 검정 이렇게 4개만 갖고 있고, 나머지 색은 전부 얘들을 적절한 배율로 섞은 망점의 조합만으로 표현한다.

컴퓨터에서 보는 사진 이미지를 프린터로 출력하기 위해서는 가산 혼합 기반인 RGB 방식의 색을 감산 혼합 CMYK 방식으로 변환하고, 색 축별 망점 배합을 계산해야 할 것이다. 이건 디더링과는 다른 영역이다. 프린터 드라이버가 하는 일 중의 하나가 이것이며, 전문적인 사진이나 출판 프로그램 역시 색 축별로 인쇄 형태의 저수준 데이터를 export하는 기능을 제공한다.

그래도 요즘은 사진조차 필름 현상이 아니라 디지털 카메라로 찍은 뒤에 포샵질을 하고 고급 인화지에다 '인쇄'해서 만들어 내는 세상이니.. 컬러 인쇄 기술도 예전보다 굉장히 많이 좋아지고 저렴해졌다. 1990년대까지만 해도 가정용으로 컬러 레이저 프린터라는 걸 생각이나 할 수 있었겠는가?

유니코드 문자 중에 U+2591 ~ U+2593은 단계별 음영을 나타낸다.
굴림· 바탕 같은 통상적인 Windows 글꼴은 이를 하프톤 형태로 표현한 반면, 함초롬바탕은 디더링 형태로 표현했음을 알 수 있다.
윤곽선 글꼴의 래스터라이즈 방식의 특성상 디더링보다는 하프톤이 부담이 덜하기도 하다. 윤곽선 글꼴은 뭔가 덩어리· 군더더기가 늘어날수록 출력 성능이 급격히 떨어지기 때문이다. 그래서 매끄러운 곡선 말고 오돌토돌, 쥐 파먹은 효과 같은 걸 표현한 글꼴은 크기도 크고 처리하기 버거운 편이다.

사용자 삽입 이미지

이상이다. 이 사이트에도 그레이스케일, ordered 디더링, 기타 휴리스틱-_- 디더링, 그리고 하프톤까지 다양한 사례가 소개되어 있으니 관심 있는 분은 참고하시기 바란다.

우리가 사는 공간이 3차원일 뿐만 아니라, 시각 정보의 기본 단위인 색깔이라는 것도 어떤 방식으로 분류하든지 결국 3개의 독립된 축으로 귀착된다는 게 신기하지 않은가? 신학에서는 이게 하나님의 속성인 삼위일체와 관계가 있다고도 말하는데, 그건 뭐 결과론적인 해석이며 물증이라기보다는 심증 수준에서 만족해야 하지 싶다.

음악에서는 음계, 음정, 화성학 같은 이론이 수학과 연결되어 오래 전부터 연구돼 왔다.
그럼 일명 color theory라고 불리는 분야는 언제부터 누구에 의해 연구돼 왔을까? RGB, CMY, HSL 사이를 변환하는 공식 같은 것 말이다. 더디링은 컴퓨터그래픽 영역이겠지만 순수하게 색에 대한 수학적인 분석은 미술과 전산학 어디에도 딱 떨어지지 않아 보인다. 내가 알기로는 전파로 영상을 주고 받는 텔레비전 기술이 개발된 20세기 초쯤에야 이런 분야가 개척됐다.

본인이 색과 관련하여 감이 오지 않고 아직도 좀 알쏭달쏭한 걸 얘기하면서 글을 맺도록 하겠다.
모니터 화면 같은 건 그 본질이 빛이며, 빛은 색을 태생적으로 지니고 있다. 그러나 다른 세상 만물들, 특히 인쇄물은 색만 있지 빛은 지니고 있지 않다. 조명을 받아야만 자기 색을 비춰 보일 수 있다.

빛은 원색이 RGB라고 여겨지며, 섞일수록 더 밝아져서 최종적으로 white에 도달하는 ‘가산 혼합’을 한다. 그러나 빛이 없는 나머지 사물의 색들은 섞일수록 더 어두워져서 최종적으로 black에 도달하는 ‘감산 혼합’을 한다. 이 정도는 이미 초등학교 미술 시간에 배운다.

다만, 빛의 3축과 색의 3축은 노랑/초록 말고 빨강/파랑 부분도 서로 미묘하게 차이가 난다는 것부터는 고등교육 이상의 영역으로 보인다. 본인도 그걸 대학 이후에나 접했기 때문이다.
왜 그런 차이가 나는지에 대해서는 논외로 하더라도, 빛이건 색이건 두 색상을 물리적으로 섞지는 말고 디더링 하듯이 오밀조밀 가까이 배치시켜 놓으면 멀리서 볼 때 정확하게 어떤 혼색이 나타날까? 이걸 잘 모르겠다.

이건 빛이든 인쇄된 색이든 차이가 없어야 하지 않을까? 그리고 만약 차이가 없다면 그 결과는 감산 혼합이나 가산 혼합 중 어느 것과도 정확하게 일치하지 않을 것이다. 그 관계가 무엇일까? 마치 산술/기하/조화 평균처럼 서로 비슷하면서도 미묘하게 다른 결과가 나오지 않을까 싶다.

이해를 돕기 위해 아래 그림을 살펴보자. 반드시 확대/축소 왜곡되지 않은 원래 크기 형태로 볼 것!! (화면 확대 배율도 96DPI/100%로 맞춰야 함)
왼쪽은 그냥 RGB(0,0,0) 검정과 RGB(255,255,255) 하양을 1:1로 섞은 것이고, 오른쪽은 RGB(0,0,255) 파랑과 RGB(0,255,0) 초록을 섞어서 청록을 만든 것이다. 여기서 섞었다는 것은 픽셀 디더링을 말한다. 그리고 우측 하단에는 본인이 보기에 이들과 가장 비슷하다고 생각하는 순색(solid color)을 칠해 보았다.

사용자 삽입 이미지

255짜리 순색 파랑 255짜리 순색 초록을 섞어서 가산 혼합이 됐다면 RGB(0,255,255) 밝은 cyan 청록이 나타나야 하겠지만 실제로는 전혀 그렇게 되지 않았다. 그런데 그렇다고 해서 평균인 128짜리의 훨씬 어두운 색이 된 것도 아니다.
본인이 보기에 가장 비슷한 순색의 명도는 대략 180~184 정도이다. 생각보다 제법 밝다. 아.. 그래서 옛날에 VGA 팔레트도 어두운 색을 무식하게 128로 지정하지 않고 170 정도의 값을 줬는가 싶은 생각이 든다. 다른 색과 섞었을 때 재현 가능한 색이 나오라고 말이다.

이런 현상을 설명하기 위해 감마 보정 등 다른 어려운 이론들도 나온 게 아닌지 추측해 본다. 디더링 알고리즘이란 게 내가 생각했던 것보다 여러 단계로 나뉘고 더 어렵고 복잡할 수도 있겠다는 생각이 든다. 적절한 명도 추출하기, 적절히 대체색으로 분비하기, 오차 보정하기 등..;; 시각 디자인의 세계는 오묘하다.

Posted by 사무엘

2020/07/06 08:35 2020/07/06 08:35
, , , ,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/1770

등산 이야기만 몇 콤보로 계속되는 와중에 오랜만에 또 프로그래밍 얘기를 좀 하겠다.

본인은 예전에 열차나 건물(대표적으로 영화관)에서 좌석 배당 알고리즘이 어떻게 될까 궁금해하면서 이와 관련된 썰을 푼 적이 있다. 그리고 이와 비슷한 맥락에서, 점을 최대한 균등하게 순서대로 뿌리는 ordered 디더링의 가중치, 다시 말해 흑백 음영 단계 테이블은 어떻게 만들어지는 것일까 하는 의문을 제기했다. 그 당시엔 의문 제기만 하고 더 구체적인 해답을 얻지는 못했다.

그래픽 카드가 천연색을 표현할 수 있게 되면서 이제 컴퓨터에서 선택의 여지가 없는 '생존형'(?) 디더링의 필요성은 전무해졌다. 비디오보다는 아주 열악한 네트워크 환경에서 그래픽의 용량을 극도로 줄일 필요가 있을 때에나 특수한 용도로 제한적으로 쓰이는 듯하다. 색상뿐만 아니라 해상도도 왕창 올라가면서 이제는 글꼴의 힌팅조차 존재감이 많이 위태로워졌을 정도이니 세상이 참 많이도 변했다.

하지만 ordered 디더링이라는 건 점을 평면이나 공간에 최대한 골고루 질서정연하게 뿌리는 순서를 구하는 문제이다 보니, 계산 알고리즘의 관점에서는 실용적인 필요성과는 별개로 굉장히 흥미로운 문제인 것 같다.

사용자 삽입 이미지
(이제는 이런 무늬 패턴을 볼 일 자체가 거의 없어졌다..)

흑과 백이 정확하게 반반씩 있는 50% 경우를 생각해 보면, 당연한 말이지만 흑과 백은 대각선으로 엇갈린 형태로 존재한다. 수평선이나 대각선 형태가 아니다. ▤나 ▥가 아니라 ▩에 가까운 것이다.

그러므로 아주 간단한 2*2 크기의 음영이라면
(1 4)
(3 2)

가 된다. 수평선인 (1 2)(3 4)나 수직선인 (1 4)(2 3)이 아니라, (1 4)(3 2)라는 것이다.
그러니 태극기의 괘는 패턴이 (3 5)(4 6)이기 때문에 수직선에 가깝다. 그리고 이거 무슨 승용차에서 운전사가 있을 때와 없을 때, 좌석의 위치별로 상석에서 말석 순서 테이블과 비슷하다는 느낌도 든다.. -_-;;

시작점인 1은 언제나 좌측 상단으로 고정해서 생각해도 일반성을 잃지 않는다. 그럼 다음 2의 위치는 1에서 가장 멀리 떨어진 대각선이므로 역시 자동으로 결정된다.
그럼 (1 4)(3 2) 대신 (1 3)(4 2)는 불가능한 방향이 아니긴 하지만, 관례적으로 2 다음에 위쪽이 아니라 왼쪽에다가 3을 찍는 걸 선호하는 듯하다.

자, 그럼 얘를 조금 더 키워서 4*4 음영은 어떻게 될까?

(1 ? 4 ?) - (1 ? 4 ?) - (1 13 4 16)
(? * ? *) - (? 5 ? 8) - (9 5 12  8)
(3 * 2 ?) - (3 ? 2 ?) - (3 15 2 14)
(? * ? *) - (? 7 ? 6) - (11 7 10 6)

테이블의 크기가 딱 두 배로 커지면 새로운 숫자들은 언제나 기존 테이블의 틈바구니에 삽입된다. 그래야 균형이 유지될 수 있다.
각각의 틈바구니에 대해서 원래 칸의 대각선 아래 (+1, +1), 그리고 바로 아래 (0, +1), 바로 옆 (+1, 0)의 형태로 (5~8), (9~12), (13~16)이 매겨진다. 그랬더니 무슨 짝수 마방진 같은 복잡난감한 퍼즐이 채워졌다.

컴퓨터그래픽에서 실용적으로 가장 많이 쓰이는 음영은 8*8 크기이다. 모노크롬/16색 시절에 단색 패턴 채우기 함수들은 전부 8*8 패턴을 사용했다. 그러므로 얘는 음영을 64단계까지 표현할 수 있다.

8*8 패턴은 역시 4*4 패턴의 틈바구니에 삽입된다. 16 다음에 17이 들어가는 위치는 어디일까? 1과 2 사이에 5가 삽입되었던 것처럼 1과 5의 사이에 17이 삽입된다. 그리고 패턴 크기의 절반인 4픽셀 단위로 n, n+1, n+2, n+3이 (x,y), (x+4,y+4), (x,y+4), (x+4,y)의 순으로 번호가 매겨지는 건 변함없다.

거의 난수표 수준의 복잡한 테이블이 완성됐다. 규칙성이 뭔가 감이 오시는지? 그래픽 라이브러리들은 마치 삼각함수 테이블만큼이나 미리 계산된 디더링 테이블을 내장하고 있다.
그런데 이런 식으로 16*16 256단계 음영 테이블은 어떻게 만들 수 있을까?
각 구간을 순서대로 각개격파하는 게 아니기 때문에 분할 정복이나 재귀호출은 아닌 것 같다.

이런 숫자를 생성하는 코드를 작성하기 위해, 먼저 다음과 같은 변수들을 클래스나 전역변수 형태로 정의하자.

int mtrix[N][N]; int cs, ce;
static const POINT PTR[4] = {
    {0,0}, {1,1}, {0,1}, {1,0}
};

void Draw(int y, int x, int delta)
{
    for(int i=0;i<4;i++)
        mtrix[y+PTR[i].y*delta][x+PTR[i].x*delta]=ce++;
}

Draw는 특정 지점에서 n 간격으로 (0,0), (n,n), (0,n), (n,0)의 순으로 ce부터 ce+3까지 번호를 매겨 주는 역할을 한다.
이를 이용하면 2*2의 경우는 Draw(0, 0, 1)을 통해 간단히 만들 수 있다.

void Case2()
{
    cs=2; ce=1; memset(mtrix, 0, sizeof(mtrix));
    Draw(0, 0, 1);
}

앞서 살펴보았던 4*4는 이런 형태가 되고..

void Case4()
{
    cs=4; ce=1; memset(mtrix, 0, sizeof(mtrix));
    for(int a=0;a<4;a++)
        Draw( PTR[a].y, PTR[a].x, 2 );
}

더 복잡한 8*8은 Draw를 어떤 순서대로 호출해야 할지 따져보면 결국 규칙성이 도출된다.
그렇다. 2중 for문이 만들어지며, 16*16은 3중 for문이 될 뿐이다.

void Case8()
{
    cs=8; ce=1; memset(mtrix, 0, sizeof(mtrix));
    for(int a=0; a<4; a++)
        for(int b=0; b<4; b++)
            Draw(PTR[a].y + PTR[b].y*2, PTR[a].x + PTR[b].x*2, 4);
}

void Case16()
{
    cs=16; ce=1; memset(mtrix, 0, sizeof(mtrix));
    for(int a=0; a<4; a++)
        for(int b=0; b<4; b++)
            for(int c=0; c<4; c++)
                Draw(PTR[a].y + (PTR[b].y<<1) + (PTR[c].y<<2),
                    PTR[a].x + (PTR[b].x<<1) + (PTR[c].x<<2), 8);
}

사용자 삽입 이미지

바로 이것이 우리가 원하는 정답이었다. 식을 도출하고 보니 규칙은 허무할 정도로 너무 간단하다. n중 for문을 재귀호출이나 사용자 스택 형태로 정리하는 건 일도 아닐 테고.
이 정도면 평면이 아니라 3차원 공간을 점으로 촘촘하게 채우는 것도 생각할 수 있다. PTR 테이블은 (0,0,0), (1,1,1)부터 시작해서 정육면체의 꼭지점을 순회하는 순서가 되므로 크기가 8이 될 것이다.

그리고 참고로 8*8 음영 행렬은 아래의 코드를 실행해서 생성할 수도 있다.

int db[8][8];
for (int y = 0; y < 8; y++)
    for (int x = 0; x < 8; x++) {
        int q = x ^ y;
        int p = ((x & 4) >> 2) + ((x & 2) << 1) + ((x & 1) << 4);
        q = ((q & 4) >> 1) + ((q & 2) << 2) + ((q & 1) << 5);
        db[y][x] = p + q + 1;
    }

내가 처음에 for문을 써서 작성한 코드는 함수로 치면 일종의 매개변수 함수이다. (t에 대해서 x(t)는 얼마, y(t)는 얼마)
그런데 저건 그 매개변수 함수를 y=f(t) 형태로 깔끔하게 정리한 것과 같다. 식이 뭘 의미하는지 감이 오시는가?

이런 걸 보면 난 xor이라는 비트 연산에 대해 뭔가 경이로움, 무서움을 느낀다.
덧셈이야 "니가 아무리 비비 꼬아서 행해지더라도 까짓거 덧셈일 뿐이지. 결과는 다 예측 가능해" 같은 생각이 드는 반면, xor에다가 비트 shift 몇 번 하고 나면 도저히 예측 불가능한 난수 생성 알고리즘이 나오고 암호화/해시 알고리즘이 만들어지기 때문이다. 지극히 컴퓨터스러운 연산이기 때문에 속도도 왕창 빠르고 말이다.

2002년에 우리나라에서 열렸던 국제 정보 올림피아드에서도 'xor 압축'이라는 제출형 문제가 나온 적이 있다. 임의의 비트맵 이미지가 주어졌을 때, 이걸 사각형 영역의 xor 연산만으로 생성하는 순서를 구하되, 연산 수행을 최소화하라는 게 목표이다.

한 점에 대해서 가로/세로로 인접한 점 3개를 추가로 조사하여 흑백 개수가 홀수 개로 차이가 나는 점을 일종의 '모서리'로 간주하여 각 모서리들에 대해 plane sweeping하듯이 xor을 시키면 그럭저럭 괜찮은 정답이 나온다. 단, 이것이 이론적인 최적해와 동일하다는 것은 보장되지 않는다. 그렇기 때문에 문제가 제출형으로 출제된 것이다.

재미있는 것은 모서리 판정도 xor로 하면 간단하게 해결된다는 것이다.
(pt[x][y]==1)^(pt[x+1][y]==1)^(pt[x][y+1]==1)^(pt[x+1][y+1]==1) 같은 식. 이유는 조금만 생각해 보면 알 수 있다.

난 Bisqwit이라는 필명을 쓰는 이스라엘의 무슨 괴수 그래픽 프로그래머의 코딩 동영상에서 저 코드가 흘러가는 걸 발견하고 가져왔다. 흐음..;; Creating a raytracer for DOS, in 16 VGA colors 뭐 이런 걸 올려서 시청자들을 경악시키는 분이긴 한데, 물론 레알 16비트 도스용 Turbo C나 QuickBasic 컴파일러로 저런 걸 돌린다는 소리는 아니다. 그건 알파고 AI를 개인용 데스크톱 컴퓨터로 돌리는 것만큼이나 불가능한 일이니 너무 쫄지 않아도 된다. (VGA 16색인 건 맞지만 메모리와 속도는 그 옛날 기계 기준이 결코 아님.)

엑셀에다가 저 16*16 음영 테이블을 입력한 뒤, 수식을 이용해서 숫자 n을 입력하면 그에 해당하는 음영이 생성되게 워크시트를 만들어 보니 재미있다. 이번에도 흥미로운 덕질을 했다.

 

사용자 삽입 이미지

Posted by 사무엘

2016/06/26 08:33 2016/06/26 08:33
, , ,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/1242

열차 좌석 배당 알고리즘

열차의 승차권을 구입하면 좌석은 어떤 식으로 배당될까?
객차 하나당 좌석은 차량에 따라 60~70개 정도가 있으며, 열차 한 편성은 일반실만 생각하더라도 최하 4량부터 시작하고 KTX의 경우 거의 15량에 가깝다. 수백 개의 좌석들은 어떤 순서와 원칙대로 승객에게 팔려 나갈까?

난 철덕후로서 그 알고리즘이 예전부터 굉장히 궁금했다. 여러분은 그렇지 않은가?

버스 정도면 그냥 아무렇게나 랜덤으로 배당해도 별 무리가 없을 것이다.
우등 고속버스는 가장 쉽다. 승차 정원부터가 30명이 채 안 되는 소규모인 데다, 좌석이 구조적으로 2개짜리와 1개짜리로 나뉘어 있으니 말이다.

단독 승객에게는 진행 방향 기준으로 오른쪽의 단독 좌석부터 먼저 배당해 주고, 그게 매진되거나 2인 승객이 있으면 2인 좌석을 준다. 상석인 맨 앞자리는 약간 나중에 팔리도록 다른 가중치를 부여하고, 반대로 최악의 자리인 맨 뒷자리는 최하위 우선순위로 팔리게 하면 될 것이다.

그러나 열차는 단순하게만 좌석을 배당해서는 대략 곤란하다.
1부터 n호차까지, 그리고 진짜 무식하게 1번부터 m호석까지 앞에서 뒤로 순서대로 꽉꽉 승객을 채워 넣어서 뒤의 객차는 텅 빈 채로 달리게 할 리는 없을 테고..

그렇다고 좌석을(특히 단독 승객) 완전 랜덤으로만 여기저기 들쭉날쭉으로 배당하면 좌석의 단편화(fragmentation)가 너무 심해진다. 그래서 승객이 얼마 타지도 않은 상태인데 이따금씩 타는 2인 이상의 다수 승객은 이어진 좌석을 못 구해서 서로 찢어져서 앉아야 하는 일이 벌어질 수 있다.

결국 본인이 추측하기로는 열차의 좌석 배당은 저 양 극단의 중간을 절충하는 방식으로 이뤄질 것 같다.
두세 개의 객차를 묶음으로 나눠서 한 묶음 안에서 좌석을 무작위로 배당한 뒤, 그 묶음의 좌석이 다 매진되면 다음 묶음으로 간다. 각 묶음은 1~3호차, 4~6호차, 7~9호차 같은 규칙으로 만들 수도 있고, 반대로 1, 4, 7호차와 2, 5, 8호차, 3, 6, 9호차 같은 규칙으로 만들 수도 있다.

그리고 각 객차 안에서는 전체의 50~60% 정도는 단독 승객이 무작위로 띄엄띄엄 앉을 수 있게 배려한다. 즉, 2개짜리 좌석이라도 한 자리에 단독 승객이 있으면 거기는 일단 건너뛰고 다른 빈 자리를 찾는다는 뜻이다. 그러나 나머지 자리는 가능한 한 2인 승객이 한꺼번에 찜할 수 있게 비워 두며, 한 객차의 좌석의 10~20% 정도는 마치 KTX 동반석처럼 4인 가족이 연속해서 앉을 수 있게, 가능한 한 1~2인 승객에게 금세 팔리지 않도록 비워 둔다.

단독 승객의 경우 창측 좌석이 내측 좌석보다 먼저 팔리게 하는 건 기본이다. 또한 열차에서는 출입문과 가까운 맨 앞이나 맨 뒤 좌석이 '안 좋은 자리'이므로 이것 역시 다른 좌석이 모두 팔린 뒤에 나중에 팔리게 해야 할 것이다.
단독 승객용 좌석과 2인 이상 승객용 좌석 영역을 정하는 것 역시 '엿장수 마음대로' 무작위로 하면 되며, 그 비율 역시 평소에 승차권이 팔리는 단위 통계를 근거로 합리적으로 정하면 될 것이다.

저런 균형적인 요소에 덧붙여 환승 동선도 고려 대상이 된다.
국내의 예를 들면 KTX 천안아산 역과 장항선 아산 역은 남쪽 끝에서 만난다. 그리고 KTX는 한 편성이 무려 400m가 약간 안 되는 매우 긴 열차이다. 그렇기 때문에 경부선 KTX를 타다가 천안아산 역에서 장항선으로 환승하는 승객은 부산 방면(하행) 열차의 경우 최대한 앞쪽 객차로 좌석이 배당되고, 서울 방면 열차는 뒤쪽 객차로 좌석이 배당된다. 지하철에서 환승을 빨리 할 수 있는 객차의 위치와 정확히 같은 개념이며, 한국 철도도 그 정도 센스는 이미 갖추고 있다.

이 정도면 내가 보기에 열차 좌석 배당 전략을 짜는 건, 마치 열차 시각표를 짜는 것에 필적하는 철도 영업 기술의 결정체가 될 수도 있을 것 같다.
현실성 있는 열차 운행 시각표를 짜기 위해서는 그 나라의 철도 인프라와 지형 특성, 차량 제원, 승객 패턴 등의 알토란 같은 영업 기밀이 총동원되어야 한다. 이런 걸 계획하는 건 인원을 더 투입한다고 신속하게 되는 게 아니며, 핵심 똘똘이 인력 한두 명이 다 도맡아 한다.

좌석 배당도 마찬가지일 거라는 말이다. 철덕이라면 반드시 정복해야 하는 분야 중 하나 되시겠다.
비행기는 무게 배분이(한쪽에만 승객 무게가 지나치게 쏠리지 않게) 좌석 배당에 감안되는 요인이라고 하는데, 철도는 무게 배분 걱정은 할 필요가 없는 대신 길다는 특성상 다른 변수가 존재하는 셈이다.

자, 여기까지만 글을 쓰려고 했는데, 빈 좌석에다 승객을 일정 규칙대로 채워 넣는 과정을 생각하자니 컴퓨터그래픽에서 중요하게 다뤄지는 알고리즘 분야가 문득 떠오르더라.
바로 디더링이다.

디더링은 적은 수의 색깔을 섞어서 더 화려한 색깔을 아쉬운 대로 표현하는 기법이다. 색을 물리적으로 섞을 수는 없으니 결국 서로 다른 색깔을 번갈아가며 늘어놔야 하는데, 한 색깔이 뭉치는 게 아니라 서로 다른 색깔들끼리 최대한 고르게 퍼지도록 픽셀을 배열해야 한다.

본인은 과거에 Windows 3.x 시절에 그림판에서 임의의 RGB 값을 주면 그 색을 16컬러만으로 디더링하여 표현하는 걸 보고 무척 신기해했었다. 가령, 흑에서 백으로 단계를 증가시킬 때, 검은색에서 흰색 점이 차츰 늘어나는 순서가 어떻게 정해지는지가 무척 궁금했다.

그 규칙을 디더링에서 threshold matrix라고 부른다. 일반적인 그래픽 프로그램에서는 8*8짜리를 사용한다. (출처는 위키백과) 저기서 1부터 16까지의 점을 순서대로 채우면 25% 음영이 그려지고, 32까지 채우면 흑백이 딱 반반씩 번갈아가며 등장하는 50% 음영이 되는 식이다.

사용자 삽입 이미지
처음에는 4픽셀 간격으로 띄엄띄엄 점을 그리고, 나중에는 그 사이의 4픽셀 간격을 채우는 식으로, 점들이 뭉치지 않고 어떤 경우에도 최대한 흩어져서 퍼져 있게 한다. 임의의 격자 크기가 주어졌을 때 threshold matrix를 생성하는 프로그램을 만들 수도 있을 법해 보이는데 그리 만만한 일은 아닌 것 같다. 마방진도 아니고 말이다.

더 나아가 임의의 색을 16컬러 디더링 패턴으로 표현해 내는 프로그램을 직접 짜 보면 어떨까? 주어진 색을 가장 가깝게 표현할 수 있는 2색 또는 3색 조합을 구한 뒤, 그 비율만큼 threshold matrix를 각각의 색으로 채우면 될 것이다. 색조합을 구하는 것은 미지수의 개수가 식의 개수보다 더 많아서 답이 하나로 딱 떨어지지 않는 부등식이 될 터이니, LP(선형 계획법) 같은 계산 기법이 동원돼야 하지 않을까 싶다.

그렇게 threshold matrix만을 정석대로 적용하면 ordered dithering이 된다. 그러나 그것만으로는 그림이 칙칙하고 보기가 안 좋기 때문에, 디더링된 색깔의 픽셀이 인접 픽셀에 시각적으로 끼치는 영향을 감안하여(error diffusion) 더 정교하게 디더링을 수행하는 알고리즘이 실생활에서 쓰인다. 더 깊게 들어가는 건 이 글의 범위를 벗어나므로 자세한 설명을 생략하겠다.

뜬금없이 디더링 얘기를 꺼낸 이유는.. 저렇게 디더링 점을 찍어 나가는 게 마치 열차 좌석을 배당하는 것과 비슷한 심상이 느껴져서이다. 열차 좌석의 점유 여부를 흑백 픽셀로 표현하고 시간이 흐름에 따라 픽셀들의 상태를 표시하는 시뮬레이션을 돌려 보면 재미있을 것 같다. 한쪽은 검은 색이 듬성듬성 있고, 한쪽은 검은 색이나 흰 색이 좀 연속해서 있겠지 아마?

철도의 좌석 배당 알고리즘과 래스터 그래픽의 디더링 알고리즘은 서로 따로 생각하고 있었던 주제인데 이렇게 한 글로 연결이 됐다. 마치 예전에 내가 열차의 급행 등급과 셸 정렬을 한데 묶어서 글을 썼듯이 말이다. 참 신기한 일이 아닐 수 없다. ㅋㅋㅋㅋ

Posted by 사무엘

2013/04/08 08:18 2013/04/08 08:18
, , , ,
Response
No Trackback , 4 Comments
RSS :
http://moogi.new21.org/tc/rss/response/815


블로그 이미지

철도를 명절 때에나 떠오르는 4대 교통수단 중 하나로만 아는 것은, 예수님을 사대성인· 성인군자 중 하나로만 아는 것과 같다.

- 사무엘

Archives

Authors

  1. 사무엘

Calendar

«   2020/09   »
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30      

Site Stats

Total hits:
1442985
Today:
315
Yesterday:
482