ISSN 2383-630X(Print) / ISSN 2383-6296(Online) Journal of KIISE, Vol. 42, No. 2, pp. 235-241, 2015. 2 http://dx.doi.org/10.5626/jok.2015.42.2.235 얼굴인식을위한연립대각화와국부선형임베딩 (Locally Linear Embedding for Face Recognition with Simultaneous Diagonalization) 김은솔 노영균 장병탁 (Eun-Sol Kim) (Yung-Kyun Noh) (Byoung-Tak Zhang) 요약국부선형임베딩 (Locally Linear Embedding, LLE) [1] 는다양체학습 (manifold learning) 알고리즘중하나로고차원공간에있는데이터들사이의내적값을기반으로임베딩하는방법이다. LLE 를이용하여임베딩한결과는독특한성질이있는데, 고차원공간상에서같은평면에있는데이터들은내적값이크기때문에저차원공간에서도가깝게위치하도록임베딩되는반면수직으로위치한평면에있는데이터들은내적값이 0 이되기때문에서로떨어진위치에임베딩된다. 한편, 한사람의얼굴에다양한각도에서조명을비추면서촬영한이미지들은저차원의선형부분공간을구성한다는사실이잘알려져있다 [2]. 이에본논문에서는다른평면에위치하는데이터들을자연스럽게분류하여임베딩하는 LLE 알고리즘을얼굴이미지에사용하여효과적으로얼굴인식문제를해결할수있는방법을제안한다. 제안하는방법은 LLE 에연립대각화 (Simultaneous Diagonalization, SD) 를적용한방법으로, S 연립대각화를적용하면데이터들이형성하는평면이수직이되도록바꿀수있기때문에 LLE 의성질을극대화할수있다. 실험결과, 연립대각화를적용하고 LLE 를적용하면서로다른사람의얼굴이미지들이겹치지않고뚜렷하게구분되는효과가있음을확인하였다. 키워드 : 국부선형임베딩, 얼굴인식, 연립대각화 Abstract Locally linear embedding (LLE) [1] is a type of manifold algorithms, which preserves inner product value between high-dimensional data when embedding the high-dimensional data to low-dimensional space. LLE closely embeds data points on the same subspace in low-dimensional space, because the data points have significant inner product values. On the other hand, if the data points are located orthogonal to each other, these are separately embedded in low-dimensional space, even though they are in close proximity to each other in high-dimensional space. Meanwhile, it is well known that the facial images of the same person under varying illumination lie in a low-dimensional linear subspace [2]. In this study, we suggest an improved LLE method for face recognition problem. The method maximizes the characteristic of LLE, which embeds the data points totally separately 이논문은정부 ( 미래창조과학부 ) 의재원으로한국연구재단의지원을받아수행된연구이며 (NRF-2010-0017734-Videome), 정부 ( 미래창조과학부및정보통신기술진흥센터 ) 의정보통신 방송연구개발사업지원 (10035348-mLife, 14-824- 09-014, 10044009-HRI.MESSI) 및삼성전자의지원을일부받았음 이논문은 2014 한국컴퓨터종합학술대회에서 얼굴인식을위한연립대각화와국부선형임베딩 의제목으로발표된논문을확장한것임 논문접수 : 2014년 9월 4일 (Received 4 September 2014) 논문수정 : 2014년 11월 14일 (Revised 14 November 2014) 심사완료 : 2014년 11월 18일 (Accepted 18 November 2014) 학생회원 : 서울대학교컴퓨터공학부 CopyrightC2015 한국정보과학회ː 개인목적이나교육목적인경우, 이저작물 eskim@bi.snu.ac.kr 의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 비회원 : 한국과학기술원전산학과교수사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시 yungkyun.noh@gmail.com 명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위 종신회원 : 서울대학교컴퓨터공학부교수 (Seoul National Univ.) 를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. btzhang@bi.snu.ac.kr 정보과학회논문지제42권제2호 (2015. 2) (Corresponding author 임 )
236 정보과학회논문지제 42 권제 2 호 (2015. 2) when they are located orthogonal to each other. To accomplish this, all of the subspaces made by each class are forced to locate orthogonally. To make all of the subspaces orthogonal, the simultaneous Diagonalization (SD) technique was applied. From experimental results, the suggested method is shown to dramatically improve the embedding results and classification performance. Keywords: locally linear embedding, face recognition, simultaneous diagonalization 1. 서론비선형임베딩 (Non-linear embedding) 방법중하나인국부선형임베딩 (Locally Linear Embedding, LLE) [1] 는고차원공간에있는데이터들의내적정보를사용하여고차원상에위치하는데이터를저차원으로사상 (mapping) 한다. 내적값은두벡터가같은방향으로있을때에최대값을가지고수직으로있을때에는 0이되는성질이있는데, 이정보를기반으로임베딩 (embedding) 을하는 LLE는고차원공간에있는데이터들이얼마나유사한방향으로위치하고있는지혹은같은평면에있는지에대한정보를기반으로데이터를사상하게된다. 특히수직으로위치하는데이터들사이의내적값은 0이므로이러한데이터들사이의내적값정보는임베딩할때에이용되지않는다. 우리는 LLE가수직으로위치하는데이터들사이의관계를고려하지않는다는점에주목하여데이터를효과적으로분리할수있는새로운방법을제안하고, 이러한방법이특히얼굴데이터의분류성능을크게향상시킬수있다는점을보이고자한다. 얼굴이미지에는 identity 이외에조명, 자세, 표정과같은외부요인이포함되어있을수있는데, 이중조명의변화는간단한선형모델로표현할수있다. 특히물체 ( 얼굴이미지에서는얼굴 ) 가 Lambertian일때에, 물체에다양한각도에서빛을비추면서이미지를촬영하면, 그이미지들은저차원선형공간 (low-dimensional linear subspace) 을구성한다는특징이알려져있다 [2,3]. 즉, 한사람의얼굴을다양한조명변화를주면서찍은사진들이있다면, 이사진들은하나의저차원선형평면을이루게된다. 이러한이미지데이터의성질때문에 LLE를이용하면자연스럽게 identity를분류할수있다. 반면거리를이용하는임베딩방법을쓰면상반된결과를얻게된다. 얼굴이미지에조명변화가포함되어있으면, 이미지들사이의거리는 identity보다는조명변화에의해결정된다. 그러므로거리를보존하는것을목표함수로하여데이터를임베딩하는 Isomap과같은알고리즘은조명의구조에따라데이터를임베딩하게된다. 그러므로얼굴이미지들을임베딩하면조명변화에따른구조가나타나고, 이결과로는 identity를구분하기힘들다. 본논문에서는 LLE가데이터가형성하는 (span 하는 ) 평면에따라데이터를임베딩하기때문에, 얼굴이미지를 identity에따라자연스럽게분류하는성질을극대화시킬수있는방법을제안한다. 데이터들이저차원선형평면을형성하고있을때, 이들을가장잘분리할수있는경우는평면이서로수직일경우이다. 그러므로본논문에서는분류하고자하는클래스마다형성되는평면이항상수직으로위치하도록변형한뒤 LLE를적용하는방안을제시한다. 클래스마다형성하는평면이수직이되도록하기위해서연립대각화 (Simultaneous Diagonalization, SD) 방법을적용하였다. 제안하는 SD-LLE 방법을실험을통해확인해본결과기존 LLE에비해 SD-LLE가얼굴이미지의분류성능을크게높일수있으며거리를기반으로하는 Isomap 보다도훨씬높은정확도를보임을확인하였다. 2. Locally Linear Embedding LLE는비선형임베딩방법중하나로서, 인접한데이터들사이의내적값 (inner-product value) 을보존하면서임베딩한다. 차원이 D 인고차원공간에데이터가 N 개있고, 한개의데이터 x i 와인접한 k(k N) 개의데이터들을 x j (1 j k) 라고하자. LLE는 x j 들의선형결합으로 x i 를재생성할때, 재생성에러를최소로하는선형결합계수 ( 가중치 ) 들을찾고, 이선형결합을차원이 d(d D) 인낮은차원의공간에서도유지하는좌표 Y i 를찾는다. 이때 Y i 의좌표가회전이나이동과같은연산에영향을받지않게하기위하여가중치의합이 1이되도록한다. 선형결합계수 W 를구하는방법은다음과같다. x i, x j 는각각크기가 D인열벡터, X i 를 x i 와인접한 k개의데이터들을나타내는 D k 행렬, W를 D N행렬이라고하자. 이때고차원공간에서의재생성에러 E 는다음과같이나타낼수있다. 이때 E 는 N개의데이터에대한재생성에러의합
얼굴인식을위한연립대각화와국부선형임베딩237 인데, 각각의재생성에러는 0보다크므로 E 를최소화하는것은각각의재생성에러를최소화하는것과같다. 즉 E i 를최소화하는 W i 를찾는문제와같다. W i 는다음과같이전개하여구할수있다. 위에서구한 W i 는주어진데이터 x i 를 k개의인접데이터 X i 가 span하는평면으로정사영시키는행렬이다. 또한 x i 와인접한데이터들중에서 x i 와수직으로위치하는데이터들에대한가중치는 0이되므로수직으로위치한데이터들사이의관계는임베딩할때에고려되지않는다. 또한목적함수에 W i 값의합이 1인조건이있는데, 이조건까지추가하여에러를최소화할경우에는 x i 를 X i 들이이루는 convex hull과가장가까운곳으로사상을하게된다 ( 그림 1). W 행렬에서볼수있듯이 LLE는데이터들사이의내적값을기반으로임베딩을하게되는데, 이러한성질은거리를기반으로하는다른비선형임베딩방법과비교하여독특한성질을가진다. 예를들어, 거리를기반으로임베딩을하는 Isomap는 [4] 고차원상에서인접한데이터들을찾고, 이러한인접데이터들과의거리를저차원공간에서도보존하는것을목표로한다. 그렇기때문에, 서로다른클래스의데이터가고차원공간상에서인접하여위치해있다면, 저차원공간상에서도가까이위치하게된다. 반면, LLE는서로다른클래스의데이터가가까이있더라도각각의클래스의데이터가 span 하는평면이서로수직이면, 데이터들을분리시켜서임베딩한다. 본논문에서는 LLE의이러한특성을극대화시켜데이터를효과적으로분류하고, 특히얼굴이미지의분류성능을높일수있는새로운방법을제시한다. 3. 연립대각화 (Simultaneous Diagonalization) 2장에서살펴보았듯이, LLE는고차원공간에서같은평면에위치하는데이터들이저차원공간에서도가깝게위치하도록임베딩을하는반면, 인접한데이터들중에서수직으로위치하는데이터들은서로멀리위치하도록한다. 그렇기때문에, 서로다른클래스에속하는데이터들이 span하는평면이서로수직으로위치할수록서로다른공간에떨어뜨려임베딩할수있게된다. 만약서로다른클래스에속한데이터들이 span하는평면이수직으로위치하고있지않거나비슷한각도를이루면서위치해있다면저차원공간에겹쳐서임베딩될수도있다. 이문제를해결하기위하여본논문에서는클래스가다른데이터들이 span하는평면이수직으로위치하도록바꾼후에 LLE를적용하는방법을제시한다. 클래스가다른데이터들이서로수직으로위치하도록하기위하여연립대각화 (Simultaneous Diagonalization, SD) 방법을적용하였다. 연립대각화는다음과같은방법으로이루어진다 ( 그림 2). 데이터가두개의클래스 X, Y 로이루어있다고하자 ( 그림 2(a)). 먼저, 클래스 X만을 whitening 시키는변형을클래스 X,Y 에동시에적용하면변형된 X 1 의공분산행렬 (covariance matrix) 가단위행렬이된다 ( 그림 2(b)). 그다음, X 1,Y 1 전체를 whitening 시켜서모든방향의분산 (variance) 가같아지도록하면그림 2(c) 와같이두클래스가수직으로위치하게된다. 연립대각화방법에대한자세한내용은표 1에정리되어있다. 그림 1 재생성에러를최소화하는 W가가지는기하학적의미. W는주어진 i번째데이터를 k개의인접데이터들이 span 하는평면으로정사영하는행렬이다. 이때가중치합이 1인조건이있기때문에 k개의인접데이터들이이루는 convex hull에가장가까운값을데이터를정사영시키는행렬이 W가된다. Fig. 1 Geometrical meaning of the W. The W is the projection matrix which maps the input data x i onto the plane spanned by k-nearest neighbors of the x i. Specifically, due to the sum-to-one constraint, the x i would be mapped to the closest point of the convex hull made by k-nearest neighbors
238 정보과학회논문지제 42 권제 2 호 (2015. 2) 그림 2 연립대각화 Fig. 2 Simultaneous Diagonalization 표 1 연립대각화과정 Table 1 Simultaneous Diagonalization method 그림 3 Yale Face Database 의예 Fig. 3 Examples for Yale Face Database 4. 실험및논의본논문에서제시하는알고리즘은두클래스의데이터가서로수직으로위치하고있지않을때 LLE를사용하면겹쳐서임베딩이되는문제가있는데, 이를해결하기위하여두클래스의데이터가수직으로위치하도록바꾼후에 LLE를적용하였다. 이알고리즘 (SD-LLE) 의성능을확인하기위해서는서로수직으로위치하지않는두클래스의데이터를임베딩을했을때 LLE보다더뚜렷하게임베딩되는결과를보여야한다. 이를위하여여러가지합성데이터를만들어성능을분석해보았다. 또한실제얼굴이미지데이터에도적용하여, 제시하는알고리즘이타당한지확인해보았다. 4.1 데이터실험을위하여 2개의클래스로구성된합성데이터와 Yale Face Database B [5,6] 를사용하였다. 합성데이터셋은두가지방법으로생성되었다. 첫번째합성데이터는총 20차원인데그중 10차원은고유차원 (intrinsic dimension) 으로서가우시안분포를따르고, 나머지 10차원은잡음차원 (noise dimension) 이다. 두번째데이터는 50차원데이터이고 10차원이고유 차원으로, 가우시안분포를따른다. 이두가지데이터에 SD를적용시킨후에 LLE를수행한결과가그림 3에정리되어있다. 그림 3의왼쪽그래프들은 SD를적용하지않고 LLE를수행한결과인데, 같은클래스에속하는데이터들이인접하여임베딩이되긴하지만, 두개의데이터가겹쳐서위치하고있다. 반면 SD를적용한후 LLE 를적용한결과를보면서로다른클래스에속하는데이터들이따로떨어져서위치하고있는것을확인할수있다. 두번째로 Yale Face Database B 중에서배경이제거되고얼굴부분만남긴이미지를이용하였다 ( 그림 3). 이미지의크기는가로 192 픽셀, 세로 168 픽셀로데이터의차원은약 30,000이며, 사람마다조명조건이다른 64장의이미지가있다. 이중에서두사람의이미지셋을뽑아실험한결과를그림 4에정리하였다. 4.2 실험결과우선합성데이터로제안하는방법의성능과효과를분석해보았다. 첫번째실험에서사용한데이터는두개의클래스로이루어진 5차원의데이터로서 5차원중 2차원이고유차원이고가우시안분포를따른다. 각각의클래스는 50개의데이터샘플을포함하고있다. 이데이터를 LLE로임베딩한결과 ( 아래, SD-LLE로표기 ) 와 SD를거친후 LLE로임베딩한결과 ( 위 ) 를그림 4에정리하였다. 데이터들이 span 하는평면이비슷한각도로위치해있을때 LLE로임베딩하면많이겹쳐서임베딩이되지만 SD-LLE를사용하면뚜렷하게구분할수있음을알수있다. 제안하는방법의효과를보다명확하게알아보기위하여 Isomap과비교해보았다 ( 그림 5). 전체가 10차원으
얼굴 인식을 위한 연립 대각화와 국부 선형 임베딩 239 그림 6 Yale Face Database를 이용한 실험 결과. 2명의 이미지(64개씩 128개, 동그라미의 색깔이 identity 를 표시함)에 LLE(왼쪽 위), SD-LLE(왼쪽 아래), Isomap(오른쪽 위), SD-Isomap(오른쪽 아래)을 적용한 결과 Fig. 6 Experimental results with Yale Face Database. Images for two identities (64 images for each 그림 4 합성 데이터를 이용한 첫 번째 실험 결과. 위: SD-LLE, 아래: LLE Fig. 4 The first experimental results with synthetic data. identity, the color of the dots represents the identity). LLE (Left top), SD-LLE (Left bottom), Isomap (Right top), SD-Isomap (Right bottom) SD-LLE (top), LLE (bottom) 그림 5 LLE와 Isomap을 이용하여 임베딩한 결과. 왼쪽 위: LLE, 왼쪽 아래: SD-LLE, 오른쪽 위: Isomap, 오른쪽 아래: SD-Isomap 그림 7 여러 가지 다양체 학습 알고리즘으로 얼굴 이미지 데이터(두 개의 클래스)를 임베딩한 결과. 왼쪽 위 Fig. 5 Embedding results with LLE and Isomap. (Left top) 부터 시계 방향으로 PCA, Isomap, LLE, SD-LLE, LTSA, Laplacian eigenmap LLE, (Left bottom) SD-LLE (Right top) Isomap, Fig. 7 Embedding results using 6 kinds of manifold (Right bottom) SD-Isomap learning algorithme. PCA, Isomap, LLE, SD-LLE, LTSA, Laplacian eigenmap (in clockwise) 로 이루어진 가운데 2차원이 고유 차원이고 가우시안을 따른다. 또 각각의 클래스에는 300개의 데이터가 포함되 데이터가 span 하는 평면들이 겹치는 부분이 많기 때문에 어 있고 두 개의 클래스의 평균은 같다. 왼쪽 두 개의 그 Isomap을 사용하여 임베딩을 하면 두 개의 클래스가 많이 래프는 LLE를 사용한 결과(위: SD 적용하지 않은 경우, 겹치게 된다. 반면 SD-LLE를 사용하면 두 개의 클래스가 아래: SD 적용)이고 오른쪽 두 개의 그래프는 Isomap으 비교적 뚜렷하게 구분되는 것을 볼 수 있다. 로 임베딩한 결과이다(위: SD 적용하지 않은 경우, 아래: 실제 얼굴 이미지를 임베딩 한 결과를 그림 6과 7에 SD 적용). 두 개의 클래스가 평균이 같아 각각의 클래스의 정리하였다. 그림 6은 두 개의 identity에 대해서 LLE와
240 정보과학회논문지제 42 권제 2 호 (2015. 2) 그림 8 LLE와 Isomap으로얼굴이미지를분류한결과. SD를사용하지않고 Isomap과 LLE로임베딩을한후에분류를한결과 ( 좌 ), SD를적용한후분류를한결과 ( 우 ) Fig. 8 Classification results for face recognition with LLE and Isomap. (Left) Classification with embedding results (Right) Classification with embedding results after SD Isomap 그리고 SD-LLE, SD-Isomap을사용하여임베딩한결과이고, 그림 7은 4개의다양체학습알고리즘들과비교한결과이다 [4,7-9]. 그림 6과 7을보면 LLE를제외한다른다양체학습알고리즘들은하나의 identity가가지고있는구조를찾는것을볼수있다. 즉조명변화가만드는다양체를환형태로표시하고있음을볼수있다. 하지만두개의 identity를분리하는데에는적합하지않은임베딩한결과이다. 반면 LLE와 SD-LLE는 identity를기준으로데이터를임베딩하며, 특히 SD-LLE는그특성을극대화하여두개의 identity를뚜렷하게분리하는것을볼수있다. 그림 8은임베딩한후얻은좌표로분류를한결과이다 (k-nn classifier, k=7). 제안하는 SD-LLE 알고리즘은두개의클래스에대해서만 SD를할수있으므로 2진분류 (binary classification) 문제로바꾸어수행하였다. Yale Face database B는 38명의데이터를제공하므로, 두명씩뽑을수있는모든조합에대해서분류를수행한후정확도의평균을계산하였다. 얼굴이미지에포함된조명변화는이미지들사이의유클리디안거리에가장큰영향을미치기때문에, 거리를기반으로임베딩하는 Isomap는조명변화에따른구조에따라데이터를임베딩하였다. 반면 LLE는데이터들이이루고있는평면에따라임베딩을하기때문에, 자연스럽게 identity에따라임베딩하며 SD를적용할경우더욱더뚜렷하게 identity를분리하면서임베딩하는것을볼수있다. 이러한임베딩결과는자연스럽게분류성능에영향을미치는데, SD-LLE의경우 LLE보다약 14% 높은정확도를보였다. 5. 결론 하는방향으로임베딩하는성질이있음을보이고, 이성질을극대화하기위하여연립대각화 (Simultaneous Diagonalization) 을결합하는방법을제안하였다. 또한제안하는알고리즘은특히얼굴이미지데이터셋에서 identity를분류하는데효과적으로사용될수있음을확인하였다. 추후연구로서는 2개이상의클래스를가지고있는데이터에대해서연립대각화를적용할수있는방법을고안하여제안한 SD-LLE가실제데이터에서더욱효과적으로사용될수있도록할예정이다. References [1] S. Roweis, L. Saul, "Nonlinear dimensionality reduction by locally linear embedding," Science 290, pp. 1212-2326, 2000. [2] M. Turk, P. Alex, "Face recognition using eigenfaces, Computer Vision and Pattern Recognition," Proc. IEEE Conference on Computer Vision and Pattern Recognition, 1991. [3] W. Zhao, R. Chellappa, P. J. Phillips, "A. Rosenfeld. Face recognition: A literature survey," Acm Computing Surveys (CSUR) 35.4, pp. 399-458, 2003. [ 4 ] Tenenbaum, J. B., De Silva, V., and Langford, J. C., "A global geometric framework for nonlinear dimensionality reduction," Science, 290 (5500), 2319-2323, 2000. [5] A.S. Georghiades, P.N. Belhumeur, D. Kriegman, "From few to many: Illumination cone models for face recognition under variable lighting and pose," Pattern Analysis and Machine Intelligence, IEEE Transactions on 23.6: 643-660, 2001. [6] K. C. Lee, J. Ho, D. Kriegman, "Acquiring linear subspaces for face recognition under variable lighting," IEEE Transactions on Pattern Analysis and Machine Intelligence, 27.5: 684-698, 2005. [7] Belkin, M., Niyogi, P., "Laplacian eigenmaps for dimensionality reduction and data representation," Neural computation, 15(6), pp. 1373-1396, 2003. [8] Zhang, Z. Y., and Zha, H. Y., "Principal manifolds and nonlinear dimensionality reduction via tangent space alignment," Journal of Shanghai University (English Edition), 8(4), 406-424, 2004. [ 9 ] Jolliffe, I. Principal component analysis, John Wiley & Sons, Ltd. 2005. 김은솔 2010년서울대학교컴퓨터공학부졸업 ( 학사 ). 2010년~현재서울대학교컴퓨터공학부박사과정. 관심분야는기계학습, 인지과학 본논문에서는 LLE 가데이터의내적값구조를보존
얼굴인식을위한연립대각화와국부선형임베딩241 노영균 2011 년 8 월서울대학교인지과학협동과정컴퓨터공학박사. 2007 년 8 월 ~2012 년 7 월미국펜실베니아대학교전자시스템학과방문연구원. 2011 년 9 월 ~2013 년 2 월서울대학교기계항공공학부박사후연구원. 2013 년 4 월 ~2014 년 12 월카이스트전산학과연구조교수. 2015 년 1 월 ~ 현재서울대학교기계항공공학부 BK 계약조교수. 관심분야는기계학습, 인지과학 장병탁 1986년서울대컴퓨터공학과학사. 1988년서울대컴퓨터공학과석사. 1992년독일 Bonn 대학교컴퓨터과학박사. 1992년~ 1995년독일국립정보기술연구소 (GMD, 현 Fraunhofer Institutes) 연구원. 1997년~ 현재서울대컴퓨터공학부교수및인지과학, 뇌과학, 생물정보학협동과정겸임교수. 2003년~2004 년 MIT 인공지능연구소 (CSAIL) 및뇌인지과학과 (BCS) 객원교수. 2007년~2008년삼성종합기술연구원 (SAIT) 객원교수. 현재서울대인지과학연구소소장, Applied Intelligence, BioSystems, Journal of Cognitive Science 등국제저널편집위원. 관심분야는바이오지능, 인지기계학습, 분자진화컴퓨팅기반뇌인지정보처리모델링