We propose a method to discover family photos from group photos using discriminative subgraphs. Group photos are represented to graphs by social contexts such as age, gender, and face position. The previous work considered the frequent subgraphs from all group photos as features for classification. The feature is a form of
bag-of-word model.
However, this approach produces numerous subgraphs, resulting in high dimensions. Furthermore, some of them are not discriminative. To solve this, we adopt a state-of-the-art frequent subgraph mining that removes nondiscriminative subgraphs. We also use TF-IDF normalization, which is more suitable for the bag-of-word model. To validate our method, we experiment in two data sets: Chen’s and ours. Our method shows consistently better performance, higher accuracy in lower feature dimensions, compared to the previous method.
최근 이미지 분류는 물체나 배경분류에 주력하고 있으며, 이미지 특징(feature)도 그에 맞춰 픽셀 정보로부터 추출된다. 그러나 여러 사람이 나타나는 사진일 경우, 촬영목적이 사람에 맞춰져 있어 물체 및 배경 분류 뿐만 아니라 관계나 이벤트와 같이 조금 더 높은 수준의 의미론적 정보(semantic)를 내포하고 있을 수 있다. 이전 연구에서는 이를 픽셀 정보에서 추출하는 것보다 성별, 나이, 얼굴 위치 등과 같은 사회적 맥락(social context)에서 더 잘 파악할 수 있다고 주장한다. 그 근거로, 사회학 관점에서 한 그룹 안에도 여러 작은 그룹(subgroup)이 존재하듯이 이를 그래프로 표현해 서브그래프(subgraph)들로 각 이미지를 재표현하는 것이 가능하다고 말한다. 이를 증명하기 위한 실험으로 총 2,444장의 가족과 비가족 그룹 분류를 하였다.
본 논문에서는 동일한 특징 추출방법을 따르되, 서브그래프를 생성하는 과정에서의 몇 가지 한계점들을 극복할 수 있는 방법과 추출된 특징값의 정규화 방식을 개선하는데 주력하여 최종적으로는 더 적은 특징값을 가지고 더 높거나 기존과 동일한 수준의 분류결과를 산출하는데 성공하였다.
먼저, 기존 연구의 서브그래프 추출 방식은 깊이우선탐색(DFS-based)기반의 후보군 생성방식으로 데이터 셋이 나타나는 최소 빈도수를 임계값으로 설정하여 그보다 작은 서브그래프는 생성하지 않는 방식이었다. 이것은 원하는 서브그래프의 양을 정확히 조절할 수 없다는 점과 얼마만큼의 서브그래프를 만들어야 이미지를 제대로 표현하는데 문제가 없는지를 측정할 수 없었다. 훈련 데이터 셋(train set)으로 여러 번의 실험을 수행해야만 어느 정도의 근사값을 구할 수 있었다. 여기에 특징선택(feature selection) 단계가 추가로 수행될 수 있는데, 이는 더 적은 수의 특징들로 동일 혹은 높은 분류결과를 얻는 것이 목표이다. 이전 연구에서는 문서빈도(document frequency)를 적용하였다고 했으나 적용시점이 서브그래프 마이닝 동안인지 직후인지에 대한 설명이 모호하였고, 우리는 두 가지 경우를 모두 실험해 보았다.
두 경우 모두, 이미 앞에서 설명한 문제를 피할 수는 없었지만 전자의 경우 대부분의 특징 선택비율(ratio)에서 우리가 채택한 알고리즘(CORK)과 70% 후반대의 비슷한 결과를 보여주었고, 후자의 경우 선택비율이 낮을 수록 50% 대의 분류결과를 보여주었다. 본 논문에서 채택한 서브그래프 생성알고리즘은 기존 연구에서 제안한 것과 동일한 전개구조를 가졌지만, 서브그래프가 생성될 때마다 탐욕적 전방탐색(greedy forward selection) 하에서 분류 정확도를 높일 수 있도록 거의 최적(near-optimal)을 보장하는 계산방식이 더해졌으므로, 차별적 그래프들을 자동으로 선별해낼 수 있다. 이 계산 방식을 설명하자면, A, B 두 개의 클래스가 존재할 때, A와 B에 둘 다 존재하거나 둘 다 존재하는 않는 이진 벡터(binary vector)가 많은 서브그래프는 품질점수가 낮아져 제거된다. 흥미로운 사실은 최소 출현빈도수라는 임계값 설정 없이도 이 품질 계산 부등식에 의해 그래프의 가지치기(pruning)가 가능하였다.
또 하나, 본 논문에서는 기존 연구에서 제시한 단어빈도(term frequency)에 의한 정규화보다 백오브워드(bag-of-word) 모델의 특징을 더 잘 나타내는 문서빈도 X 역문서빈도(TF-IDF) 가중치에 의한 정규화를 제안하였고, 대부분 실험결과에서 약1% ~ 4% 정도 더 높은 분류결과를 보여주었다.
