머신러닝 옥타브 실습(7-3): K-평균으로 이미지압축
온라인 강의 플랫폼 코세라의 창립자인 앤드류 응 (Andrew Ng) 교수는 인공지능 업계의 거장입니다. 그가 스탠퍼드 대학에서 머신 러닝 입문자에게 한 강의를 그대로 코세라 온라인 강의 (Coursera.org)에서 무료로 배울 수 있습니다. 이 강의는 머신러닝 입문자들의 필수코스입니다. 인공지능과 머신러닝을 혼자 공부하면서 자연스럽게 만나게 되는 강의입니다.
Programming Exercise 7:
K-means Clustering and Principal Component Analysis (K-평균 클러스터링과 주성분 분석)
1. K-means Clustering (K-평균 클러스터링)
1.4 Image compression with K-means
(K-평균을 이용한 이미지 압축)
In this exercise, you will apply K-means to image compression. In a straightforward 24-bit color representation of an image, each pixel is represented as three 8-bit unsigned integers (ranging from 0 to 255) that specify the red, green and blue intensity values. This encoding is often refered to as the RGB encoding. Our image contains thousands of colors, and in this part of the exercise, you will reduce the number of colors to 16 colors.
By making this reduction, it is possible to represent (compress) the photo in an efficient way. Specifically, you only need to store the RGB values of the 16 selected colors, and for each pixel in the image you now need to only store the index of the color at that location (where only 4 bits are necessary to represent 16 possibilities).
In this exercise, you will use the K-means algorithm to select the 16 colors that will be used to represent the compressed image. Concretely, you will treat every pixel in the original image as a data example and use the K-means algorithm to find the 16 colors that best group (cluster) the pixels in the 3- dimensional RGB space. Once you have computed the cluster centroids on the image, you will then use the 16 colors to replace the pixels in the original image.
이번 실습은 K-평균 알고리즘을 이미지 압축에 적용합니다. 이미지의 각 픽셀을 빨강, 녹색 및 파랑 색상에 대해 각각 8비트(0에서 255까지 범위)로 표시하여 24비트로 표현합니다. 색상을 이렇게 표현하는 방식을 RGB 인코딩이라고 합니다. 수천 개의 색상으로 구성된 이미지를 16 색으로 표현합니다.
K-평균 클러스터링으로 이미지를 압축하는 효과를 얻을 수 있습니다. 16개 색상의 RGB 값 저장을 저장한 24비트의 색상 사전을 만들고, 각 픽셀에 4비트의 색상 인덱스만을 저장합니다.
이번 실습은 K-평균 알고리즘으로 이미지를 압축합니다. 원본 이미지의 모든 픽셀을 데이터 예제로 취급하고 K-평균 알고리즘을 사용하여 3차원 RGB 공간에 픽셀을 16가지의 클러스터링을 합니다. 이미지의 클러스터 중심을 계산한 후에 16가지 색을 사용하여 원본 이미지의 픽셀을 대체합니다.
1.4.1 K-means on pixels
In Octave/MATLAB, images can be read in as follows:
% 128x128 컬러 이미지(bird_small.png)를 로드
A = imread('bird small.png');
% imread 함수를 사용하기 위해 이미지 패키지가 필요합니다.
% 이미지 패키지가 없다면, bird_small.mat 파일을 사용할 수 있습니다.
% load('bird small.mat');
This creates a three-dimensional matrix A whose first two indices identify a pixel position and whose last index represents red, green, or blue. For example, A(50, 33, 3) gives the blue intensity of the pixel at row 50 and column 33.
The code inside ex7.m first loads the image, and then reshapes it to create an m × 3 matrix of pixel colors (where m = 16384 = 128 × 128), and calls your K-means function on it.
After finding the top K = 16 colors to represent the image, you can now
assign each pixel position to its closest centroid using the findClosestCentroids function. This allows you to represent the original image using the centroid assignments of each pixel. Notice that you have significantly reduced the number of bits that are required to describe the image. The original image required 24 bits for each one of the 128×128 pixel locations, resulting in total size of 128 × 128 × 24 = 393, 216 bits. The new representation requires some overhead storage in form of a dictionary of 16 colors, each of which require 24 bits, but the image itself then only requires 4 bits per pixel location. The final number of bits used is therefore 16 × 24 + 128 × 128 × 4 = 65, 920 bits, which corresponds to compressing the original image by about a factor of 6.
imread() 함수는 이미지의 픽셀 위치를 나타내는 두 개의 인덱스와 빨강, 초록, 파랑, 초록 색 중에 어떤 색인지를 나타내는 인덱스를 이용해 3차원 행렬 A를 생성합니다. 예를 들어 A(50, 33, 3)은 50행 33열에 있는 픽셀의 파란색 밝기를 나타냅니다.
ex7.m 파일은 먼저 이미지를 로드한 다음 이미지를 재구성하여 m X 3 픽셀 행렬을 만듭니다. m = 128 X 128 = 16384 행이고 K-평균 함수를 호출합니다.
이미지를 나타내는 상단 16색을 찾은 후 findClosetCentroids.m 파일은 각 픽셀 위치를 가장 가까운 클러스터 중심에 할당합니다. 각 픽셀을 클러스터 중심에 할당하고 원본 이미지를 나타냅니다. 이미지를 나타내는 비트 수를 크게 줄일 수 있습니다. 실제 이미지는 128 X 128 X 24 = 393,216 비트입니다. K-평균 클러스터링은 16 색을 이미지 사전 형태로 오버 헤드 스토리지가 필요하고 각 이미지 사전은 24비트가 필요하지만 픽셀마다 색깔을 표현하는 것은 4비트만 필요합니다. 따라서 최총 비트수는 16 X 24 + 128 X128X4 = 65,920 비트입니다. 원본 이미지를 약 6배 정도 압축한 효과입니다.
Finally, you can view the effects of the compression by reconstructing the image based only on the centroid assignments. Specifically, you can replace each pixel location with the mean of the centroid assigned to it. Figure 3 shows the reconstruction we obtained. Even though the resulting image retains most of the characteristics of the original, we also see some compression artifacts.
You do not need to make any submissions for this part of the exercise.
마지막으로 클러스터 중심 할당을 기반으로 이미지를 재구성하여 압축 효과를 볼 수 있습니다. 특히, 각 픽셀 위치에 클러스터 중심의 평균으로 바꿀 수 있습니다. 그림 3은 재구성한 정보를 보여줍니다. 그 결과 이미지는 원본의 대부분의 특성을 유지하더라도 일부 압축 효과를 볼 수 있습니다.
이번 실습을 제출할 필요는 없습니다.
< Part 4: K-평균 클러스터링과 픽셀 >
(1) 이미지 업로드
clear ; % 옥타브 프로그램에 모든 변수를 제거
close all; % 터미널 이외의 창을 닫음
clc % 터미널을 깨끗이 정리
A = double(imread('bird_small.png'));
이미지를 불러올 때 사용하는 함수는 imread()입니다. imread() 함수는 이미지의 각 픽셀을 2차원 인덱스로 불러들이고 RGB 색깔의 강도를 표시합니다.
A = imread('bird_small.png')); % bird_small.png 파일을 옥타브 프로그램에 업로드
예를 들어, 50행 33열 픽셀의 색깔은 다음과 같이 표시합니다.
>> A(50,33,:)
ans =
ans(:,:,1) = 183 % 빨간색의 밝기 정도
ans(:,:,2) = 121 % 초록 색의 밝기 정도
ans(:,:,3) = 48 % 라랑 색의 밝기 정도
imread() 함수로 읽은 원래 이미지를 보기 위해 사용하는 함수는 imagesc()입니다.
>> imagesc(A)
(2) 이미지 정규화
이미지 행렬 A의 값을 0과 1 사이에 두기 위해 정규화합니다.
A = A /255;
img_size = size(A);
(3) 3차원 행렬을 2차원으로 재배열
이미지 행렬 A는 128 X 128 X 3차원 행렬입니다. K-평균을 사용할 수 있도록 3D 차원 행렬을 2D차원 행렬로 변환합니다. 행렬을 재 정렬할 때 사용하는 함수는 reshape()입니다.
>> B = 1:10
B =
1 2 3 4 5 6 7 8 9 10
>> B = reshape(B, [2 5])
B =
1 3 5 7 9
2 4 6 8 10
또한, 다차원 배열을 2차원으로 변경할 수 있습니다.
>> B = ones(4,4,2)
ans(:,:,1) =
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
ans(:,:,2) =
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
>> reshape (B, 16,2)
ans =
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
reshape() 함수를 이용해서 2차원으로 재정렬합니다. 2차원 이미지의 픽셀 위치를 1차원의 인덱스로 정리하여 실제 값은 RGB 색상의 강도를 나타내는 값을 나타냅니다. 따라서 데이터 행렬 X는 16384 X 3 행렬입니다.
X = reshape(A, img_size(1) * img_size(2), 3);
>> X
X =
0.858824 0.705882 0.403922
0.901961 0.756863 0.466667
0.894118 0.749020 0.482353
...
(4) K-평균 클러스터링 실행
기본 변수를 선언합니다.
K = 16;
max_iters = 10;
처음 시작할 때 클러스터 중심을 무작위로 초기화하는 것이 중요합니다. 지난 실습에서 작성한 랜덤 초기화 kMeansInitCentroids.m 파일을 사용합니다.
initial_centroids = kMeansInitCentroids(X,K);
>> initial_centroids = kMeansInitCentroids(X,K)
initial_centroids =
0.078431 0.082353 0.074510
0.976471 0.929412 0.698039
0.207843 0.227451 0.207843
0.137255 0.149020 0.156863
0.807843 0.709804 0.494118
0.066667 0.066667 0.054902
0.082353 0.074510 0.074510
0.447059 0.305882 0.250980
0.164706 0.192157 0.160784
0.078431 0.078431 0.082353
0.305882 0.294118 0.298039
0.847059 0.745098 0.478431
0.647059 0.458824 0.494118
0.980392 0.956863 0.745098
0.188235 0.180392 0.156863
0.058824 0.070588 0.054902
그리고, K-Means 함수를 실행합니다. 이미지에 사용된 많은 색들을 16가지 색깔로 클러스터링을 합니다.
[centroids, idx] = runkMeans(X, initial_centroids, max_iters);
>> [centroids, idx] = runkMeans(X, initial_centroids, max_iters);
K-Means iteration 1/10...
K-Means iteration 2/10...
K-Means iteration 3/10...
K-Means iteration 4/10...
K-Means iteration 5/10...
K-Means iteration 6/10...
K-Means iteration 7/10...
K-Means iteration 8/10...
K-Means iteration 9/10...
K-Means iteration 10/10...
현재 이미지가 가장 많이 사용하는 16가지 색깔을 클러스터 중심으로 만듭니다.
>> centroids
centroids =
0.094906 0.102189 0.091532
0.927198 0.814645 0.641545
0.438367 0.330018 0.228375
0.164188 0.167426 0.160408
0.805619 0.693767 0.502160
0.066531 0.072254 0.062097
0.078637 0.085382 0.074725
0.660780 0.488720 0.245127
0.242497 0.244930 0.258027
0.118421 0.127733 0.118318
0.476893 0.423265 0.420112
0.851193 0.633348 0.338823
0.584215 0.579393 0.623450
0.950456 0.928923 0.815389
0.320106 0.222092 0.161541
0.054576 0.060092 0.050515
< Part 5: 이미지 압축>
(1) 16개의 색깔로 데이터 행렬 X에 정렬
K-평균 클러스터링으로 10회 반복하여 16개의 클러스터 중심(Cluster centroids) 값을 얻었습니다. 데이터 행렬 X의 각 예제마다 가장 가까운 클러스터 중심을 idx에 저장합니다. idx는 1에서 16 사이의 값을 가지며, 총 16384개의 예제에 대한 색인입니다.
idx = findClosestCentroids(X, centroids);
>> idx. % idx는 16가지 색깔
idx =
12
5
5
5
...
idx 값을 바탕으로 각 픽셀에 매핑된 색상을 바탕으로 이미지를 복구할 수 있습니다. X_recovered 변수에 16384개의 데이터에 색깔의 위치를 나타내는 인덱스가 아니라 직접 색깔의 값을 입력합니다.
X_recovered = centroids(idx, :);
따라서, X_recovered는 16384 X 3차원 행렬입니다.
(2) 이미지 데이터로 복원
16384 X 3차원 행렬 X_recovered를 원래 이미지 데이터 형식인 3차원 데이터로 재정렬합니다.
X_recovered = reshape(X_recovered, img_size(1), img_size(2), 3);
그리고 데이터를 표시합니다. 두 개의 데이터를 비교하기 위해 하나의 그림 창에 모두 표시합니다. 이때 사용하는 함수는 subplot()입니다.
subplot(1,2,1);
imagesc(A);
title('Original');
다음 두 번째 창에 C_recovered 데이터를 표시합니다.
subplot(1,2,2);
imagesc(X_recovered);
title(sprintf('Compressed, with %d colors.', K));
1.5 Optional exercise: Use your own image
옵션 실습 : 다른 이미지로 실습
In this exercise, modify the code we have supplied to run on one of your own images. Note that if your image is very large, then K-means can take a long time to run. Therefore, we recommend that you resize your images to managable sizes before running the code. You can also try to vary K to see the effects on the compression.
이번 실습은 실습 이미지가 아닌 다른 이미지를 사용하여 진행합니다. 이미지 사이즈가 너무 크다면 오랜 시간이 걸릴 수 있으므로 이미지 사이즈를 조절할 필요가 있습니다. K의 값을 바꾸면서 테스트할 수 있습니다.
<해설 : K의 크기 바꾸기>
(1) 32개 색상을 사용한 이미지 복원
5비트를 사용하여 좀 더 많은 K= 32로 클러스터링을 할 경우 좀 더 선명한 데이터를 얻을 것입니다.
K = 32;
max_iters = 10;
initial_centroids = kMeansInitCentroids(X,K);
[centroids, idx] = runkMeans(X, initial_centroids, max_iters);
idx = findClosestCentroids(X, centroids);
X_recovered = centroids(idx, :);
X_recovered = reshape(X_recovered, img_size(1), img_size(2), 3);
subplot(1,2,1);
imagesc(A);
title('Original');
subplot(1,2,2);
imagesc(X_recovered);
title(sprintf('Compressed, with %d colors.', K));
K 사이즈를 바꾸는 것만으로 훨씬 더 많은 시간이 걸렸습니다.
(2) K=8 이미지 압축
K = 8;
max_iters = 10;
initial_centroids = kMeansInitCentroids(X,K);
[centroids, idx] = runkMeans(X, initial_centroids, max_iters);
idx = findClosestCentroids(X, centroids);
X_recovered = centroids(idx, :);
X_recovered = reshape(X_recovered, img_size(1), img_size(2), 3);
subplot(1,2,1);
imagesc(A);
title('Original');
subplot(1,2,2);
imagesc(X_recovered);
title(sprintf('Compressed, with %d colors.', K));
(3) K= 4 이미지 압축
K = 4;
max_iters = 10;
initial_centroids = kMeansInitCentroids(X,K);
[centroids, idx] = runkMeans(X, initial_centroids, max_iters);
idx = findClosestCentroids(X, centroids);
X_recovered = centroids(idx, :);
X_recovered = reshape(X_recovered, img_size(1), img_size(2), 3);
subplot(1,2,1);
imagesc(A);
title('Original');
subplot(1,2,2);
imagesc(X_recovered);
title(sprintf('Compressed, with %d colors.', K));
(3) K= 2 이미지 압축
K = 2;
max_iters = 10;
initial_centroids = kMeansInitCentroids(X,K);
[centroids, idx] = runkMeans(X, initial_centroids, max_iters);
idx = findClosestCentroids(X, centroids);
X_recovered = centroids(idx, :);
X_recovered = reshape(X_recovered, img_size(1), img_size(2), 3);
subplot(1,2,1);
imagesc(A);
title('Original');
subplot(1,2,2);
imagesc(X_recovered);
title(sprintf('Compressed, with %d colors.', K));
K-평균 알고리즘이 얼마나 대단한 아이디어인지를 한눈에 알 수 있습니다. 이미지를 단순화하거나 압축할 때 정말 효율적으로 사용할 수 있습니다.
