Matrix Decomposition and Image Processing via MATHEMATICA

 

Contents :

 

    (1) Introduction

    (2) Matrix Decomposition

    (3) Image Processing using SVD

    (4) Wave File Processing using SVD

    (5) Conclusion

 

 

성균관대학교 수학과

 

양 정 모, 김 덕 선, 이 상 구

 

            

우리는 복잡한 문제를 행렬로 바꾸어 행렬문제를 풀고 다시 그 행렬을 처음 문제의 상황에 적용하여 해석하는 경험을 자주 한다. 그러나 행렬계산에 있어서 가장 큰 문제는 행렬의 크기가 커짐에 따라 곱셈 등 여러 가지 경우에 그 계산이 복잡하여 컴퓨터를 이용하더라도 효율성에 대한 문제가 제기된다. 이에 주어진 행렬을 좀더 간단하고 다루기 쉬운 행렬들로 분해하면 계산에 있어서 속도와 효율성을 높일 수 있다. 또한 주어진 행렬을 여러 가지 방법으로 분해했을 때, 각각의 분해된 행렬들의 성질을 연구하여 처음 행렬의 정보를 크게 변화시키지 않으면서도 계산 속도와 크기를 조절하여 원래 의도했던 해를 구하는 것또 그 과정에서 얻어지는 수학적 이론은 그 이외의 문제의 해결에도 이용할 수 있다. 이것이 행렬 분해의 동기가 된다.

여기서는 주어진 행렬 A의 LU분해, QR분해, SVD(Singular Value Decomposition)를 소개하고 그 분해하는 과정을 MATHEMATICA를 이용하여 실제로 구현되는 예를 통하여 다양한 분야에서의 이용을 확인할 것이다. 그리고 SVD를 이용하여 이미지 압축 및 소리 압축 등을  MATHEMATICA를 이용하여 확인하고 그 효율을 분석하고자 한다. MATHEMATICA는 이러한 과정을 보여주기에 굉장히 편리한 사용자 환경(User Interface)를 지원한다. 이러한 환경지원은 복잡한 이미지 구현에 큰 효과를 보여준다. 이미지 압축에 사용될 SVD방법은 원래의 이미지를 크게 손상시키지 않으면서 이미지의 용량을 줄여나가는 과정을 보여주는 강력한 방법임을 확인할 수 있다. 또한 원래의 이미지에 노이즈(noise, 잡음)가 섞인 그림을 노이즈를 소거해 가며 원래의 이미지를 복원하는 데도 SVD방법이 어떻게 사용되는지를 확인할 것이다.

이 방법의 기본 아이디어는 주어진 이미지를 행렬로 바꾼 후 다시 SVD를 사용하여 세 개의 행렬의 분해를 하는 것이다. 여기서 생겨난 한 행렬의 Singular 값의 개수를 조정하여 가장 효율적인 이미지 압축을 할 것이다.

추가로 같은 방법을 사용하여 사운드를 압축하고 노이즈를 제거하는 과정도 확인해 볼 것이다. 이러한 응용은 최근 점점 많아지는 각종 Multimedia data에 대한 처리를 좀 더 수월하게 할 수 있는 효과를 보여준다. 실제로 Multimedia data들은 기본적으로 대용량의 자료들이다. 이들을 행렬 표현으로 바꾸어 SVD 등의 방법을 이용해서 압축한다면 각종 전송에 있어서도 유리할 것이다. 그러나 실제로 현재 출시된 많은 압축 프로그램에는 SVD 이외에 다양하게 매체마다 유리한 알고리즘을 택하고 있다. 그러나 SVD의 장점은 대용량의 자료를 처리하는데, 다른 알고리즘보다 빠른 속도를 보인다. 그러므로 어느 정도의 자료의 손실이 있더라도 큰 영향을 미치지 않는다면 그 효율성을 높일 수 있다. 또한 MATHEMATICA는 MATLAB에 비해서 사용자 중심의 interface가 강하고 잘 알려져 있으므로 교육적 효과를 극대화하려는 의도로 택한 것이다.

이 연구의 의의는 수학이론이 멀티미디어 자료를 다루는데 어떻게 응용되는지를 살펴보고 수학을 공부하는 의미를 되새기는 한편, 보다 효율적인 이미지 압축기술을 개발하여 실제 적용할 수 있는 기반을 다지는 데 있다.

 

 

[정리] SVD(Singular Value Decomposition)

 

  계수(rank)가 실계수 행렬 에 대하여, 행렬

로 분해할 수 있다. 여기서 행렬 는 대각선 성분이 실수로서 아래의 성질을 만족하는 대각성분이

,

대각행렬이고, 는 각각 , 직교행렬들이다.

  이때, 행렬 의 대각선성분 를 행렬 singular values라 하며,은 대칭행렬(symmetric) 의 고유값이 되며, 이들은 유일하게 정해진다. 한편, 행렬 의 열(column)들은 의 고유벡터들이며 각각을 행렬 의 left singular vectors라 하고, 행렬 의 열(또는 의 행)들은 의 고유벡터들이며 각각을 행렬 의 right singular vectors라 한다.

 

[참고] The Reduced Singular Value Decomposition방식

 

 실제로 MATHEMATICA에서는 빠른 Singular Value Decomposition을 계산하기 위하여, zero singular value를 제외한다. 이 경우, 각 행렬에서는 zero singular의 값만큼 즉, U에서는 column과 V에서는 row를 빼 주고 계산하게 된다.

 

  이러한 Reduced SVD Algorithm은 일반적인 SVD Algorithm과 달리 일단 zero singular value를 배제하고 계산함으로서 행렬 계산의 속도를 굉장히 많이 향상시킬 수 있으며 일반적으로 SVD가 쓰이는 많은 압축기술에 유용하게 사용될 수 있다.

 

4. Matrix Decomposition in MATHEMATICA

 

  ① LU-Decomposition in MATHEMATICA

  ② QR-Decomposition(또는 QR-Factorization) in MATHEMATICA

  ③ SVD Visualization in MATHEMATICA

 

 

 

 

 

        Out[43]//MatrixForm=

 

        Out[45]//MatrixForm=

 

 

 

 

 

 

 

⑶ Image Processing using SVD

 

■ 일반적인 Image를 SVD를 이용한 처리방법

 

1. 이미지를 해석하여 matrix로 변환하는 작업

2. 변화된 행렬을 SVD에 적용.(분해된 matrix 3개의 행렬처리)

3. Singular value의 개수를 조정.

4. 조정된 singular value를 이용한 행렬의 재결합

5. 재결합된 행렬의 이미지화

6. 처음의 이미지와 처리된 이미지와의 비교

SVD는 실제로 상당히 많은 분야에 응용되고 있다. 실제로 많은 데이터들이 행렬을 이용하여 처리가 되고 있으며, 실제로 데이터 전송이라든지, 데이터 압축시 그 손실을 최소로 하고, 그 결과를 이용하여 좀 더 효과적인 결과물을 얻기 위해 노력하고 있는데, 실제로 SVD은 이러한 분야에 매우 큰 쓰임새가 있다.

Image에 대한 SVD의 응용image의 압축(특히 최대한 원상을 유지하면서), 그림의 노이즈 제거등에 많이 쓰인다. 이러한 응용을 실제의 그림을 가지고 보자.

 

1. 일반적인 Image에 대응하는 연산방법

 

일반적으로 사용하는 Image파일에 대해서는 RAW형식만을 사용하고 있기 때문에 사전에 일반적인 Image를 RAW데이터로 바꿀 필요가 있다. 게다가 현재 시도하는 경우는 256까지의 지수를 이용하고 있다. 따라서 GrayScale이나 256Color만을 지원하는 그림만을 계산할 수 있다. 이를 일반적인 이미지에 대응하여 구현하기 위해서는 다음과 같은 사항들이 필요하다.

 

1. 256진수로 이루어진 3색 bit plane(RGB:Red, Green, Blue의 빛의 삼원색으로 이루져있다.)을 해석하여 Matrix로 변환하는 작업. (따라서 Matrix도 3개가 필요해진다. 이 세개의 Matrix에 대해 모두 SVD를 적용하여야 하기 때문에 용량이 많이 필요하게 된다.)

2. 이를 Color화면에 Raster(수평선 주사)시키는 작업.

실제로 RAW형식의 그림중 용량이 클 경우에는 Matrix가 엄청나게 커진다. 이를 임의의 용량이 작은 이미지로 실행해 보자.

 

임의의 RAW파일을 만들기 위한 제작은 다음과 같다.

1. 먼저 JPG나 GIF등의 파일 하나를 선택한다.

(본인은 본교 Logo파일[skkulogo.jpg]를 선택했다.)

2. 다음에는 이 파일을 Gray-Scale을 만들었다.

(MATHEMATICA에서는 메모리의 한계가 있기 때문에 일단 MATHEMATICA에서는 흑백만으로 계산을 해 보자. PhotoShop이 가장 작업하기 쉽다.)

3. RAW로 저장한다. 일반적으로 본 작업은 Photoshop (v.5.5)에서 하면 편리하게 할 수 있다.

4. skkulogo.raw라는 파일을 만들어서 다음과 같은 과정을 거쳐보자.

 

이 파일안에는 특수코드가 포함되어서 MATHEMATICA의 Kernel이 그 값을 읽을 수 없기 때문에 MATHEMATICA에서 제공하는 파일입출력함수를 써야 한다.

이 예제는 총 288×288의 그림이다. 따라서 이를 계산하면 총 82,944의 수가 나온다. 실제로 이 파일의 용량도 82,944바이트이다.

   peo의 Byte값을 수치화하여 peoma로 읽어들인다.

참고로 보통의 화일 복사시 예를 들어 512Byte씩 끊어서 읽어들이는 반면 MATHEMATICA는 그림을 읽는데 1Byte(0에서 256사이의 값)) 값을 하나씩 읽어들여 수치화하여 그 작업을 82944번 수행하므로 이 작업에서 PentiumIII 700Mhz로 실행하였는데도 1시간 가량의 계산 시간이 요구되었다. 앞으로 진행되는 그림 정보는 이미 읽어들인 그림을 바탕으로 설명될 것이다.  

 peoma에 입력된 일렬도 나열된 수치를 288개씩 택하여 288행으로 288?88 행렬화 시킨다.

      여기서 /256 은 256 지수를 1이하의 값으로 만든다.

 peoMat를 SVD시켜 UpT, psings, VpT로 분해한다.

 자 이번에는 그림에서 Singular Value가 226개나 나왔다.

이번에는 singular value 중 0.9이하의 값은 무시하도록 하자. 그러면, 145까지의 값만을 취한다.

 145개의 singular value를 택한 것을 psmallsings로 정의하자.

 UapT를 정의

 VapT를 정의  

 UapT의 transpose와 psmallsings의 대각행렬, VapT를 곱하여 newpeoMat로 정의   

 newpeoMat를 Image화 하면

그 대로의 그림이 나온다. (거의 차이를 알아보기 힘들다. ) 압축비울은 얼마인지 보자.

 UapT, VapT, psmallsings의 값을 일렬로하여 크기를 구하면 83665Byte가 된다.

원래 크기인 130,402Byte보다 46,737Byte(약 46Kbyte) 작은 83,665Byte가 나왔다.(원화의 약 65%) 즉, 65%의 memory만 이용해도 거의 원상을 그대로 복원함을 확인했다는 의미이다. Singular Value가 더 감소할수록 더 압축이 될 것이다. Singular value의 개수를 50까지 크게 줄여보자.

 28,850byte(38Kbyte)이다. 원화가 130,402(130Kbyte)이므로 약 22.1%이다.

      그림의 선명도는 약간 떨어졌음을 볼 수 있다.

Singular value의 개수를 70으로 해보자.

압축된 그림의 크기는 40KByte(40,390Byte)정도(원화의 약  31%)이다. 이 정도를 표현하기 위해선, 실제로 226여개의 Singular Value중에서 70여개의 Singular값만을 취하면 된다.

이는 SVD과정에서 singular value가 크기순으로 배정되어 대각행렬화했으므로 singular value의 개수를 조정하여도 처음에 주어진 그림의 정보를 크게 손상시키지 않으면서 압축률을 높일 수 있었던 것이다. 이는 SVD 이론적 근거가 압축률의 증가에 대한 정확한 설명을 해주는 부분이다. 이 연구의 근본적인 의의가 여기에 있다.

한편 실제 우리가 여기서 SVD를 이용한 압축에 의해 얻은 이미지 압축과정은 기존의 JPEG압축기술과 압축률에 있어서 거의 동일하다.

 

2. 일반적인 이미지에 대한 Noise 발생

 

동일하게 이번에도 한번 Noise를 발생시켜서 그 경과를 살펴보자.

점들의 형태로 Noise가 발생했다. 이 노이즈는 전 화면의 1/25의 비율로 발생하며, 그 수치는 0.5에서 임의의 값을 뺀 것이다. noiseMat 는 이 값을 원래 peoMat의 각각의 성분에 더한 것으로 정의한다. 결과적으로 noiseMat의 Singular value의 개수는 288개이고 크기는 166,176Byte로 peoMat의 130,402Byte보다 커졌다.  Noise의 처리를  위하여 그 singular value의 개수를 100로 줄이는 작업을 실행시키자.

흰색 이미지이기 때문에 그림 자체가 그리 깔끔해 보이지는 않는다. 그러나 검은 점들이 많이 흰색으로 접근한 것을 보여주고 있다. 또한 실제용량보다도 줄어들었다는 것도 알 수 있다. Singular Value의 개수를 50까지 줄여보자.

이젠 전과같이 가상의 점들은 거의 흰색이 되었다. 그러나 이미지 주변으로는 아직 노이즈가 남아 있다.

 

SVD를 이용한 압축기술은 처음 이미지에 원하지 않은 noise가 발생했을때, singular value의 개수를 줄여가면서 점점 noise의 제거를 할 수 있는 장점이 있다. Noise 제거의 원리는 noise의 정보가 filtering 시킬 경우에 원래의 이미지의 정보보다 더욱 빨리 제거된다는 데 있다. Noise제거의 원리에서도 행렬의 singular value의 지배적인 값들에 의해서 이미지가 결정되는 아이디어가 쓰인 것을 알 수 있다.

 

⑷ 소리파일에 대한 적용

 

■ SVD 이용한 소리파일의 압축방법

 

1. 소리파일을 불러들여 행렬화 시킨다.

2. 변환된 행렬을 SVD를 이용하여 분해한다.

3. 분해된 행렬의 singular value 의 개수를 조정한다.

4. 압축된 행렬을 소리로 복원한다.

5. 처음 소리파일과 음질 및 크기 등을 비교한다.

 

1. 소리파일에 대한 SVD 처리기술 적용

 

  위의 이미지 압축기술을 그대로 응용할 경우 이것은 소리파일에도 적용이 가능하다. 이를 위하여 소리파일을 MATHEMATICA에서 취급할 수 있도록 다음의 패키지를 먼저 인식시키자.

파일을 읽어드리자. 이 파일은 본인이 마이크로 직접 제작한 WAV파일이다.

 

" 성균관대학교 선형대수학 연구실입니다." 라는 멘트입니다.

 

직접 들어보자.

 

ListPlay[chimes,SampleRate->22050,PlayRange->{-2^15,2^15}]

 

ListPlot[chimes, PlotRange->{-2^15,2^15}]

 소리파일의 정보를 파형으로 살펴본 것이다.

      이 리스트는 총 파형이 -32767에서 32767사이의 데이터로 이루어져있다. 따라서 16bit의 음질을 가지고 있음을 알 수 있다.

 이 파일의 실제길이다. 약 93Kbyte정도로 이루어져있다.

 이것을 행렬로 쪼개어 sndMat로 정의하자.

 행렬로 처리된 음성화일을 들어보자.

 

ListPlay[Flatten[sndMat],SampleRate->22050,PlayRange->{-2^15,2^15}]

 sndMat를 SVD시켜 UsndT, sndsings,VsndT로 저장하자.

      sndsings에 Singular Value들이 저장이 되어 있는데 그 수가 305개다.

 총 길이는 186,355byte, 약 186Kb이다. 이 값은 원화인 93K의 두배정도이다. 이 크기를 줄이기 위해서 305개의 Singular Value에서 103개만 선택해보자.

(Singular값이 104번째부터는 10000이하의 값으로 떨어지므로 상대적으로 작은 값이 된다.)

U와 V도 각각 103개씩을 취한다.

 newsndMat를 새로 정의한 행렬들의 곱으로 만든다.

 

ListPlay[Flatten[newsndMat],SampleRate->22050,PlayRange->{-2^15,2^15}]

 newsndMat의 소리를 들어보자. 음질이 어떤가? 거의 차이가 없다. 용량을 살펴보자.  

 62933byte, 63Kb정도다. 실제 비율은 67%로 압축된 효과가 나타났다. 즉 2/3가까이로 용량이 준 것이다.

 

ListPlot[Flatten[newsndMat], PlotRange->{-2^15,2^15}]

위의 그래프에서 볼 때도 실제 변화는 거의 없어 보인다.

이제 Singular Value의 갯수를 50개까지 더 낮추어 소리를 들어보고 크기를 비교하자.

음질상의 변화는 뚜렷히 느낄 수 없다. 그러나 30550byte를 기록하므로서 원래의 33%까지 그 용량이 줄었다. 즉 67%의 압축률을 보였다.SVD의 압축효과를 소리파일에서도 확인할 수 있다. MATHEMATICA는 소리 파일 처리에 대한 함수가 내장되어 있으므오 실제 구현하는데 시간 등의 제약이 줄어들었다. 이미지 압축보다 실제적인 구현 과정의 제현에 있어서 음성화일이 더 효과적임을 알 수 있다. 교육에 적용하여 실습할 경우에 음성화일이 더 효과적이라고 생각된다.

 

 

2. 음질상에서의 Noise 처리

 

우리가 위의 그림에서 수행한 내용이 과연 음질에서도 통용될 지 한번 해 보자. 위와 동일하게 Noise를 삽입시킨다.

 

이미지의 경우와 유사하게 1/20의 비율에 60000을 곱한 값을 30000에서 뺀 값을 원래의 sndMat의 성분에 각각 더하여 noiseMat을 만든다.

변화된 noiseMat의 소리를 들어보고 파형그래프에서의 점형태 noise를 확인할 수 있다. noiseMat의 singular value와 SVD 분해후 화일 크기도 알아보자.    

지지직하는 노이즈와 함께 샘플 예제를 들었다.

이를 SVD로 처리해 보자. 먼저 Singular Value의 개수를 25개로 잡아보자.

잡음이 조금 사라진 훨씬 나아진 소리를 들려준다. 더 singular value의 개수를 더 낮추어서 들어보자.

훨씬 잡음이 감소했다. 그러나 음질도 떨어지기 시작함을 알 수 있다.

이상과 같이 소리 파일에서도 noise의 제거 과정을 살펴볼 수 있었다.

SVD에 의한 압축은 장점과 단점을 같이 갖고 있는데, 단점중의 하나가 noise의 처리과정에서 원음의 회손이 그것인데, 이는 SVD의 장점으로 생각할 수 있다.

대용량의 자료일 경우 어느정도의 작은 데이터의 손실을 가져 오더라도 그 속도면에서 다른 압축기술과 차이가 있는데, 이 손실을 최소화 하면서 압축 속도를 유지하는 것이 SVD를 이용한 압축기술 연구의 숙제이고, 현재 활발히 연구되고 있다.

우리는 이 논문에서 우리가 학습하는 수학이론의 visualization을 통해 수학이론의 유용성과 지식의 숙지도를 높이는데 software의 역할을 다시  번 생각해볼 수 있다.  

 

 

⑸ Conclusion(결론)

 

  지금까지 행렬분해의 MATHEMATICA를 이용한 실제 구현과 이미지 처리 및 소리파일 처리과정을 살펴보았다.

 

  본 연구의 의미는 크게 두  지 측면으로 볼 수 있다. 첫째는 교육적 측면이고, 둘째는 대용량 멀티미디어 데이터의 처리기술 개발에 있다.

 

첫째, 고급 수학 이론은 실제의 응용(이미지 압축, 암호처리 등)에 많이 사용되는데 본 연구는 이 중 SVD이론이 이미지 및 소리파일 처리에 쓰이는 과정을 보여줌으로써 고급수학의 응용성에 대한 동기를 부여하였습니다. 또한 소프트웨어를 통한 구현은 수학이론의 숙지도와 학습성취도를 높일 수 있다.

 

둘째, 본 연구는 대용량의 멀티미디어 자료의 처리에 있어서 이론적 연구를 통한 가장 효율적인 툴의 개발이 목적이다. SVD기술은 기존의 JPEG(Fourier transformation)이나 MPEG기술보다 대용량의 처리에 있어서 속도의 우월성을 가진다.

 

아래 Reference에서 보듯이 최근 SVD를 이용한 데이터처리에 관한 연구가 활발하다. 지금까지의 연구를 바탕으로 위의 의미를 살리는 데 노력하겠다.

 

 

 

References

 

1. Drma\v c, Zlatko New accurate algorithms for singular value decomposition of matrix triplets. SIAM J. Matrix Anal. Appl. 21 (2000), no. 3, 1026--1050 (electronic).

 

2. Demmel, James Accurate singular value decompositions of structured matrices. SIAM J. Matrix Anal. Appl. 21 (1999), no. 2, 562--580 (electronic).

 

3. Demmel, James; Gu, Ming; Eisenstat, Stanley; Slapni\v car, Ivan; Veseli\'c, Kre\v simir; Drma\v c, Zlatko, Computing the singular value decomposition with high relative accuracy. Linear Algebra Appl. 299 (1999), no. 1-3, 21--80.

 

4. Colm Mulcahy, John Rossi, Polar decomposition, singular value decomposition, pseudo-inverse and the method of least squares.

 

5. C. Ogden, T. Huff, Singular value decomposition and image processing and its applications(preprint)