로버트 플로이드

기타 업적

플로이드-스타인버그 디더링 알고리듬

자연 현상은 수치로 표현될 경우가 많다. 예를 들어 온도를 나타내기 위해 ‘섭씨 25.4도’와 같은 식으로 표현한다. 그런데 이런 수치를 컴퓨터로 다루다 보면 오차가 발생할 수밖에 없는 경우가 많다. 그것은 컴퓨터가 수치를 다루기 위해 할당하는 저장공간의 크기가 한정되어 있기 때문이다. 8비트로 데이터를 다루는 컴퓨터라면 정수값은 을 넘을 수 없다. 이를 극복하기 위해 부동소수점 방식을 사용하기도 하지만 이런 경우도 소수점 이하의 자릿수에 한계가 있다.

이미지 데이터를 다룰 때도 유사한 문제가 생긴다. 컴퓨터는 이미지를 픽셀 단위로 쪼갠 후에 저장하거나 처리한다. 이때 이미지의 실제 물리적인 값이 그대로 반영되지 못하고 컴퓨터가 다룰 수 있는 범위 내의 값으로 변환되면서 왜곡이 발생한다. 다음과 같은 극단적인 경우를 생각해보자. 아래와 같은 원본 흑백 사진을 흑백 프린터로 출력하려고 한다.

그런데 이 흑백 프린터는 각 도트(즉, 픽셀)에 대해 검은색 점을 찍거나 아니면 찍지 않는, 두 가지 선택지만 제공한다. 실제 흑백 사진은 각 픽셀이 나타낼 수 있는 정도가 완전 하얀색에서부터 조금 어두운 색, 아주 어두운 색, 완전 검은색까지 다양하다. 하지만 프린터는 오로지 점을 찍거나 안 찍는, 양자택일만 제공하므로 아주 곤란한 상황이 되어 버린다. 이때 쉽게 선택할 수 있는 방법은, 어떤 회색값을 기준으로 해서 그것보다 어두운 픽셀은 검은색 점으로 찍어내고 그것보다 밝은 픽셀은 점을 찍지 않는 것이다. 그렇게 했을 경우의 이미지 출력은 아래와 같을 수 있다.

원본 이미지를 떠올리기 어려울 정도로 많이 왜곡되어 버렸다. 그래서 이 문제를 해결하기 위해 나온 방법이 디더링^dithering이다.

실제 정보 값을 컴퓨터(혹은 프린터)가 다룰 수 있는 형태로 변환하는 과정을 양자화^quantization이라고 하고 이때 발생하는 오차를 양자화 오차라고 부른다. 디더링이란 양자화 오차의 영향을 줄이기 위한 작업이다.

플로이드가 루이스 스타인버그^{Louis Steinberg}와 함께 제안한 디더링 방식은, 각 픽셀(도트)의 양자화 오차를 바로 인접한 픽셀들에게 조금씩 적용한다. 이렇게 되면 인접한 픽셀 사이에서 양자화 오차가 급격히 달라지는 현상이 완화된다.

플로이드-스타인버그 알고리듬은, 주어진 이미지의 좌측상단 픽셀부터 시작해서 오른쪽으로 한 픽셀씩 진행하면서 디더링 작업을 진행한다. 픽셀에서 양자화 오차를 구하게 되면 위의 그림에서 보이는 것처럼 오른쪽과 아래쪽에 있는 인접한 네 개 픽셀에 그 양자화 오차의 일부 비율을 더해준다. 위의 그림에서 e는 B 픽셀에서 구한 양자화 오차이다. e가 계산되면 그것의 7/16만큼을 오른쪽에 있는 픽셀의 데이터값에 더해주고 있다. 각 픽셀이 8비트 값을 가지는 그레이 스케일^{gray scale}의 이미지 파일을 흑백 프린터용으로 디더링한다고 가정해보자. 그리고 양자화 공식은 픽셀값/255를 반올림한다고 가정한다. 위의 그림에서 B픽셀의 값이 96이라면 B픽셀을 양자화한 결과값은 0이고 양자화 오차는 96이다. 그러면 96 * 7 / 16 = 42가 C픽셀의 값에 더해진다. 이런 식으로 D픽셀에는 18, E픽셀에는 30, F픽셀에는 6이 더해지면 B픽셀에 대한 디더링이 완료된다. 이제 C픽셀로 넘어가서 같은 과정을 반복한다.

이는 오차확산^{error diffusion}이라는 방식의 일종이다. 실제로 플로이드는 디더링이라는 표현보다는 확산이라는 표현을 더 선호했다고 한다. 플로이드-스타인버그 디더링을 사용했을 때의 결과는 아래와 같다.

전자 출판의 시대가 본격적으로 도래할 수 있었던 배경 중의 하나로 플로이드-스타인버그 디더링 알고리듬이 있다고 말해도 과언은 아닐 것이다.

튜링상을 수상할 정도면 당대의 대가라고 할 수 있을 텐데 의아하게도 로버트 플로이드에 관한 자료는 별로 남아 있지 않다. 그와 아주 가까웠던 도널드 커누스가 여러 번 그에 대한 기억을 글로 남겼을 뿐, 다른 글은 찾기 어렵고 인터뷰 자료도 전무하다. 도널드 커누스의 글에서 그 단서를 하나 찾을 수 있다.

밥(플로이드)에게는 관심사가 많았다. 예를 들어 그는 세계적 수준의 백가몬^backgammon 플레이어였다. 그는 스탠퍼드에서 고급 독문학 강의안을 만드는 데 관여했다. 그는 등산과 암벽 등반을 열정적으로 좋아했고 시에라네바다 산맥의 자연을 사랑했다. 하지만 아주 소수의 친한 친구들만이 그의 이런 관심사를 알고 있었다. 왜냐하면 그는 사생활을 굉장히 숨기는 경향이 있기 때문이었다.^​2​

또 다른 이유를 들자면 그가 피크 병에 걸려서 일찍 의사소통이 불가능한 상태가 되었다는 점이다. 그는 1994년에 스탠퍼드 대학교 교수 자리에서 물러나며 은퇴했는데 1997년경부터는 지인을 알아보지 못했다고 한다. 컴퓨터 과학계가 역사에 관심을 가지고 본격적으로 유명 인사를 인터뷰하기 시작한 것이 20세기 말부터이므로 인터뷰를 할 수 있는 타이밍을 놓쳤을 가능성이 높다.

그의 이력을 보면 1965년에 카네기 멜런 대학교에 채용되었으므로 30년 동안 교수직에 머물렀다. 그런데 그에 비해 그의 밑에서 박사 학위를 받은 이는 7명에 불과하다.^​15​ 그것도 겨우 3년 동안 머무른 카네기 멜런 대학교에서는 3명인 반면에 27년을 머무른 스탠퍼드 대학교에서는 4명에 불과하다.

하지만 스탠퍼드에서 그의 밑에서 박사학위를 받은 4명의 면면을 보면 대단하다고 할 수 있다. 4명 모두 유수의 대학에서 후학을 양성하고 있으며 특히, 로버트 타잔^{Robert Tarjan}과 로널드 리베스트^{Ronald Rivest}는 후에 튜링상을 수상했다.^​§§​

스탠퍼드 시절에 지도한 박사과정 학생이 그렇게 적었던 이유는 알려진 바가 없다. 참고로, 그의 이름이 포함된 논문이 1980년대에 들어오면서 급격히 줄어든다. 흥미롭게도 이 시기는 그의 친구인 도널드 커누스가 TeX 개발에 몰두하던 시기와도 겹치는데, 커누스에 따르면 플로이드는 강의에 치중하면서 Chiron이라는 이름의 새로운 프로그래밍 언어를 설계하고 있었다고 한다. 이 언어는 몇 가지 혁신적인 아이디어를 담고 있었는데 결국 구현되지 못했다.^​2​

플로이드가 세상을 떠난 후에 스탠퍼드 대학교에서는 그를 추억하는 글을 공식 발표했다. 그 글에 따르면 플로이드는 소프트웨어 리팩토링^refactoring을 최초로 주장한 사람으로 언급하고 있다.

플로이드는 리팩토링을 최초로 주장한 사람일지 모르겠다. 이미 동작하고 있는 프로그램을, 필수 아이디어만 유지한 채로 바닥에서부터 다시 작성하자고 제안했다… 같은 일을 하지만 더 간단한 방법을 계속 찾아나감으로써 프로그램 그 자체뿐만 아니라 프로그래머의 능력과 이해도를 개선해야 한다고 플로이드는 말했다.^​3​

(c) 이재범, 2023
이 콘텐츠는 대한민국 저작권법의 보호를 받습니다. 작성된 모든 내용의 권리는 저자에게 있으며, 저자의 동의 없는 사용은 금합니다. 본 콘텐츠의 일부 혹은 전체 내용을 무단으로 전재/복제/배포하거나 2차적 저작물로 재편집하는 경우, 법적 책임을 지게 됩니다.

1 2 3 4 5