BLOG :||

2. 다트 게임(난이도: 하)

카카오톡에 뜬 네 번째 별! 심심할 땐? 카카오톡 게임별~

카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다.
갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다.

1. 다트 게임은 총 3번의 기회로 구성된다.
2. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.
3. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수^1 , 점수^2 , 점수^3 )으로 계산된다.
4. 옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
5. 스타상(*)은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상(*)의 점수만 2배가 된다. (예제 4번 참고)
6. 스타상(*)의 효과는 다른 스타상(*)의 효과와 중첩될 수 있다. 이 경우 중첩된 스타상(*) 점수는 4배가 된다. (예제 4번 참고)
7. 스타상(*)의 효과는 아차상(#)의 효과와 중첩될 수 있다. 이 경우 중첩된 아차상(#)의 점수는 -2배가 된다. (예제 5번 참고)
8. Single(S), Double(D), Triple(T)은 점수마다 하나씩 존재한다.
9. 스타상(*), 아차상(#)은 점수마다 둘 중 하나만 존재할 수 있으며, 존재하지 않을 수도 있다.

0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.

입력 형식

“점수|보너스|[옵션]”으로 이루어진 문자열 3세트.
예) 1S2D*3T

• 점수는 0에서 10 사이의 정수이다.
• 보너스는 S, D, T 중 하나이다.
• 옵선은 *이나 # 중 하나이며, 없을 수도 있다.

출력 형식

3번의 기회에서 얻은 점수 합계에 해당하는 정수값을 출력한다.
예) 37

입출력 예제

문제 해설

문제에서 토큰화를 이용해서 풀라고 했는데 단어 단위로 문제를 풀었다. 한 번 푼 내용은 보존하고 다시 풀어야 할 것 같다.

단어 단위로 끊을 경우엔 별 어려움이 없다. 각 글자가 특수기호인지 아닌지를 구분하여 숫자를 넘겨주고, 그대로 활용하면 된다. 문제점이라면 java를 안쓴지 오래되서 입력법도 해깔렸다.

문자열 문제 다루는 것에는 C++보다 Java가 쉽더라.

package kakao02;

import java.util.Scanner;
public class kakao02 {

	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		String dart;
		dart = sc.next();
		int arr[] = new int[3];
		int result = 0;
		int count = 0;
		String tempNum ="";
		for(int i = 0; i<dart.length();++i)
		{
			if(dart.charAt(i) =='S')
			{
				arr[count] = Integer.parseInt(tempNum);
				tempNum = "";
				arr[count] = (int)Math.pow(arr[count], 1);
				count++;
			}
			else if(dart.charAt(i)=='D')
			{
				arr[count] = Integer.parseInt(tempNum);
				tempNum = "";
				arr[count] = (int)Math.pow(arr[count], 2);
				count++;
			}
			else if(dart.charAt(i)=='T')
			{
				arr[count] = Integer.parseInt(tempNum);
				tempNum = "";
				arr[count] = (int)Math.pow(arr[count], 3);
				count++;
			}
			else if(dart.charAt(i)=='*')
			{
				if(count==1)
				{
					arr[count-1] *=2;
				}
				else
				{
					arr[count-2]*=2;
					arr[count-1]*=2;
				}
			}
			else if(dart.charAt(i)=='#')
			{
				arr[count-1]*= -1;
			}
			else
			{
				tempNum+=dart.charAt(i);
			}
		}
		result = arr[0] + arr[1]+arr[2];
		System.out.println(result);
	}
}

4
1 5 6 7

10

5
10 9 8 7 6

50

10
1 1 2 3 5 8 13 21 34 55

55

10
5 10 11 12 13 30 35 40 45 47

50

4
5 2 8 10

20

4
3 5 15 16

18

다이나믹 프로그래밍 문제라고 친구에게 받았지만 앞서 풀었던 문제들과 느낌이 달라서 당황스러웠다.

생각한 과정은 처음에 n 개당 얼마라는 가격이 정해져 있는데,

만약 2개를 파는 가격이 2개 가격보다 1개씩 두 개 파는 경우가 더 비싼 경우, 해당 숫자는 필요없게 된다.

P2의 존재가 의미 없어지고 P1 + P1이 P2의 가격을 대체하게 된다. 이를 MaxPrice[개수]로 별도 저장한다.

그런 식으로 쭉 각 개수에 대한 최대값을 기록하다보면 

MaxPrice[n]의 값을 구하기 편해진다. MaxPrice[n] = MaxPrice[n-i] + MaxPrice[i]( 0<= i <= n/2)가 된다.

3개 이상을 더해서 MaxPrice[n]을 구할 수 있지 않나 생각할 수 있는데 3개 이상의 항이 있을 때, 모든 항을 더해야 n의 개수와 같아지기 때문에 모두 MaxPrice가 존재한다. 따라서 두개의 항 밖에 존재하지 않는다.

#include <iostream>
#include <stdio.h>
using namespace std;
int price[1001] = {0};
int maxprice[1001] = {0};
int checkMaxPrice(int n)
{
      if(n == 1)
      {
          maxprice[n] = price[n];
          return maxprice[n];
      }
    else if(maxprice[n] != 0)
    {
        return maxprice[n];
    }
    else
    {
        int max = price[n];
        for(int i = 1; i<= n/2;++i)
        {
        	if(max < checkMaxPrice(i) + checkMaxPrice(n-i))
        		max = checkMaxPrice(i) + checkMaxPrice(n-i);
        }
        return maxprice[n] = max;
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i = 1; i<=n;++i)
    {
        cin>>price[i];
    } 
    int max = checkMaxPrice(n);
    cout << max;
    return 0;
}

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

예제 입력 1

3

예제 출력 1

2

학교에서 한번도 다이나믹 프로그래밍에 대한 이야기를 들어본 적이 없었다. 학교 커리큘럼에 안타까움을 느낀다.

인터넷의 다른 답안에서는 피보나치를 이야기 하는데, 피보나치 여부를 문제 풀 당시에는 인지하지 못했고, 

끝자리가 1이냐 0이냐에 따라 변화는 관계를 이용하여 문제를 풀었다. 

n-1 자리에서 끝자리가 0인게 x 개이고 1인게 y 개일 때, n 자리의 끝자리가 0인 이친수의 개수는 x+y 개이고, 

1인 이친수의 개수는 x 개이다. 라는 내용을 기반으로 문제를 풀었다.

int는 안되고, unsigned int도 안되고 long long을 해야 되는 개수에 놀랐다.

#include <iostream>
#include <stdio.h>

using namespace std;

struct Pinary
{
	long long oneT = 0;
	long long zeroT = 0;
	//unsigned int oneP = 0;
	//unsigned int zeroP = 0;
};
Pinary pinaryArray[90];


Pinary PinaryCheck(int n)
{
	if (n <= 1)
	{
		pinaryArray[n - 1].zeroT = 0;
		pinaryArray[n - 1].oneT = 1;
		return pinaryArray[n - 1];
	}
	else if (pinaryArray[n - 1].zeroT != 0 || pinaryArray[n - 1].oneT != 0)
	{
		return pinaryArray[n - 1];
	}
	else
	{
		Pinary t = PinaryCheck(n - 1);
		pinaryArray[n - 1].zeroT = t.zeroT + t.oneT;
		pinaryArray[n - 1].oneT = t.zeroT;
		return pinaryArray[n - 1];
	}
}

int main()
{
	int n;

		cin >> n;

		Pinary t = PinaryCheck(n);
		cout << t.zeroT + t.oneT;
    return 0;
}

2017.09.16 카카오 신입공채 1차 코딩 테스트 문제

1. 비밀 지도(난이도: 하)

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어  위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 “공백”(“ “) 또는 “벽”(“#”) 두 종류로 이루어져 있다.

2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 “지도 1”과 “지도 2”라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.

3. “지도 1”과 “지도 2”는 각각 정수 배열로 암호화되어 있다.

4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

입력 형식

입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.

  1 ≦ n ≦ 16

  arr1, arr2는 길이 n인 정수 배열로 주어진다.

  정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2^n - 1을 만족한다.

출력 형식

원래의 비밀지도를 해독하여 "#", 공백으로 구성된 문자열 배열로 출력하라

출력 형식

원래의 비밀지도를 해독하여 "#", 공백으로 구성된 문자열 배열로 출력하라.

입출력 예제

 취업 춘비를 위해 알고리즘을 하나씩 풀고 있다. 문자열 문제는 짜증나서 자바로 풀고 있지만 그 외의 수열 계산 문제는 C++로 풀려고 노력한다.

문제 풀이를 보니 비트 연산자 문제였었다. 비트 연산자가 뭐였지 하고 한참 생각하다가 검색해보고 풀게 되었다.

다음에는 검색없이 비트 연산자를 기억해낼 수 있기를..

result의 경우에는 arr2 하나하나 받을 때마다 바로 연산을 해줘도 된다.

arr2가 들어오자마자 arr와 비트연산자를 해서 arr에 다시 집어넣는 것이 메모리 절약에 더 좋을 것 같다.

if(((int)pow(2, n-1-i) & result[j] == (int)pow(2, n-1-i))의 부분은 비트 연산자를 통해 특정 자리의 이진수만 남겨놓으려 했을 때

같다면 해당 자리에 이진수가 존재하는 것이고 없으면 아니라는 판단하에 작성했다.

#include 
#include <stdio.h>
#include<string>
using namespace std;
int main()
{
	int arr[16];
	int arr2[16];
	int result[16];
	string wall[16] = { "" };
	int n;
	//1 0000# 2 000#0 4 00#00 8 0#000 16 #0000
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin>> arr[i];
	}
	for (int i = 0; i < n; ++i)
	{
		cin>> arr2[i];
	}
	for (int i = 0; i < n; ++i)
	{
		result[i] = arr[i] | arr2[i];
	}
	for (int j = 0; j < n; ++j)
	{
		for (int i = 0; i < n; ++i)
		{
			if (((int)pow(2, n - 1 - i) & result[j]) == (int)pow(2, n - 1 - i))
			{
				wall[j] += "#";
			}
			else
			{
				wall[j] += " ";
			}
		}
	}
	for (int i = 0; i < n; ++i)
	{
		cout << wall[i] << endl;
	}

    return 0;
}

https://github.com/codecoding/SQLite4Unity3d

https://tyle.io/

가격이 조금 비싸다.

참고: https://www.csie.ntu.edu.tw/~cjlin/libsvm/

마지막 과제로 머신 러닝을 이용한 특징점 검출을 했다.

보고서를 따로 작성한 내용이 있어서 목차와 표지, 파일 설명 부분을 제외하고 그대로 옮겼다.

파이어폭스로 글을 옮기면 자꾸만 브라우저가 꺼진다..

줄간격 맞추기도 어렵다.

코드는 맨 하단에.

1. 개요

LBP를 이용하여 특징점에 대한 Training database를 만든 후, 머신 러닝을 이용하여 학습을 통해 적절한 특징점을 찾아낼 수 있는 모델을 완성하는 것을 목표로 한다.

2. Training database 생성

1) SIFT를 이용한 특징점 검출

먼저 Training database를 만들기 전에 특징점을 검출할 수 있는 기능이 있어야 한다. 기존에 과제에서 작성했던 SIFT Detector를 이용해서 특징점을 검출한다.

다만, 기존 SIFT Detector는 검출되는 특징점의 양이 많아서 활용하기에 적절하지 못하므로 약간의 수정을 가한다.

기존 SIFT Detector는 2개의 Octave에 각각 6장의 Gaussian Filter, 5장의 DoG(Difference of Gaussian)을 사용했지만 특징점의 개수를 줄이기 위하여 1 Octave에서 4번째 DoG에서 검출되는 특징점만 이용하기로 한다.

기존 코드를 바꾸는 것도 좋지만 검출 시간에 큰 영향을 미치지 않기에 기존 제출된 과제물에서 약간의 수정을 한다.

극점을 판단 하는 위치에

if (1.6*pow(2, (o + d) / 3.0) > 3.2)

줄여서 다시 작성하면  

if (((o + d) / 3.0)>1)

위와 같은 코드를 작성함으로써 특징점 검출 개수를 줄일 수 있다.

수정된 SIFT 이미지(좌측), 기존 SIFT 이미지(우측)

database에 삽입될 LBP 정보는 특징점을 기준으로 11x11의 패턴을 LBP를 이용하여 자신을 제외한 총 120개의 값을 받아서 저장한다.

LBP 패턴의 값을 뽑아올 때는 특징점을 중심으로 일정 거리의 값들을 비교하여 저장하기 때문에 이미지의 일정 범위의 테두리는 검토하지 않는다. Padding을 시도할 경우, 그만큼 저장할 feature이 늘어나기 때문에 사용하지 않는다.

여러가지 LBP 크기를 검토해보았으나 3x3, 5x5는 크기가 너무 작아서 제외하고 7x7은 각 픽셀에 대한 모든 LBP feature를 저장했을 때 이미지 10장 기준 약 300MB의 database가 나왔다. 500장 기준 15GB의 용량을 차지하며, 15x15의 경우 18GB의 용량을 차지한다.

11 x 11을 사용한 이유는 크기가 너무 작거나 크지 않고 넓이가 128에 가장 근접했기 때문이다. 특징점 중복 제거를 위한 값을 이용할 때, 사용하기 적합하다고 판단했다.

BSD500의 이미지를 전부 사용할 경우, Positive feature: 25,921개, Negative feature: 73,214,579개가 나온다.

2) 특징점 중복 제거

특징점이 가질 수 있는 경우의 수는 2^{(LBP의 넓이-1)} 이다. 

11 x 11의 경우,1,329,227,995,784,915,872,903,807,060,280,344,576 만큼의 경우의 수가 존재한다. 경우의 수가 많기 때문에 각 패턴이 같을 경우는 거의 없지만 같은 경우가 있다면 가치가 떨어진다고 판단했다.

처음 시도한 방법은 각 특징점의 패턴을 기록하기 전에 Vector 컨테이너에 존재하는 값들과 비교를 한 후, 중복이 없으면 Vector 컨테이너에 추가 삽입을 하면서 모든 패턴을 비교한 후에 training database를 생성하는 것을 시도했다.

LBP는 특징점의 픽셀과 주변 픽셀과의 크기 비교를 통해 1 또는 0의 값만 보관하므로 bitset을 이용하여 값을 보관하도록 했다. Bitset은 각 1비트씩 값을 저장하기 때문에 11x11의 LBP 패턴을 보관할 비트 배열을 생성 및 저장하도록 한다.

Vector 를 이용해서 새로 들어올 패턴과 기존의 패턴들을 비교할 때, Vector는 입력된 자료의 순서대로 저장을 하기 때문에 값을 비교할 때 Vector에 저장된 양이 많아질 수록 느리다. 한 이미지의 특징점 검출 및 Vector에 삽입하기까지 처음에 1초가 걸렸다면 그 다음엔 2초, …., 10초로 점점 숫자가 늘어나더니 한 이미지 당 1분이 넘게 걸리게 된다.

Map 컨테이너는 중복 체크 및 정렬에 특화된 컨테이너이다. 특정 값의 삽입을 시도하면 중복 여부를 체크하고 자동으로 정렬해준다. <key, value>의 형식으로 이루어져 있기 때문에 key가 있어야 한다. value에는 LBP 패턴이 들어가고, key에는 중복 및 순서를 확인하기 위한 정보가 들어간다. 앞서 말했듯이 LBP 패턴의 종류는 2^{(LBP의 넓이-1)} 이다. 이를 구분하기 위해서는 120bit를 넘어가는 값을 저장할 수 있어야 한다. 따라서 별도의 구조체를 생성한다.

typedef struct int256 { __int64 a = 0; __int64 b = 0;__int64 c = 0;__int64 d = 0;

           bool operator < (const int256 &rhs) const {

                     if (d != rhs.d) return (d < rhs.d);

                     if (c != rhs.c) return (c< rhs.c);

                     if (a != rhs.a) return (a < rhs.a); return (a < rhs.a); } };

64bit 변수를 4개를 가지고 있기 때문에 최대 256bit까지 값을 보관할 수 있다. oprator < 함수는 map 컨테이너가 구조체를 가지고서 비교 및 정렬을 할 수 있게 해주는 연산자 오버로딩 함수이다. 최대 256bit까지 허용한 이유는 15x15를 테스트하기 위함이다.

Map 컨테이너를 사용할 경우, feature 검출에 이미지 별로 약 400~600ms의 시간이 소요된다. 많은 양의 이미지를 집어넣어도 빠르게 중복 검출 및 정렬을 할 수 있다는 점이 큰 장점이다.

feature 검출 소요 시간 및 정보

중복 제거를 할 경우, Positive feature: 23,578개, Negative feature: 54,438,407개가 나온다. Positive feature의 경우 2,343개의 중복 feature를 제외했으며, Negative feature의 경우 18,776,172개의 중복 feature를 제거했다. 이를 통해 제한된 용량의 database에 들어갈 feature의 종류를 더욱 다양하게 해준다.

3) Database에 삽입될 특징점 선정

중복을 제거했지만 database에 전부 집어넣기엔 많은 용량이 필요하다. 모든 feature를 집어넣었다고 해도 Train에 많은 시간을 필요로 하게 된다. 검출된 feature 중에서 적절한 feature를 선정해서 적은 용량과 짧은 시간으로 model을 만들어야 한다.

Positive Feature는 약 5000개를 이용하기로 한다. 25000개를 넣고, Negative Featue를 3배 정도 넣었을 때도 상당한 시간이 걸렸기 때문에 1/5로 축소한 값이다. 

Negative Feature는 Positive Feature의 약 2000배지만 이를 다 집어넣을 수 없기 때문에 Positive의 3배에 해당하는 양을 database에 삽입한다.

Database에 삽입할 때, 삽입 기준은 Random 및 임계값 사용 등 다양한 방법이 있지만 map이 자동 정렬을 해주기 때문에 조금 더 단순한 방법을 사용한다.

Map은 Key 값에 따라 삽입을 할 때마다 정렬이 된다. Key값은 LBP feature의 값을 나타낸다. LBP의 넓이가 n일 때,

LBP Feature의 Key값은 p[0]*2⁰+p[1]*2¹+p[2]*2²+…+p[n-1]*2^n-1 이 된다.

즉, LBP 패턴에 따라 Key값이 정해지며 이를 통해 특정 Key값에서의 LBP 패턴 모양을 알 수 있다. Map은 Key값을 자동으로 정렬해주므로 LBP Feature도 점진적인 형태로 정렬이 되어있다. 3x3 LBP의 경우, 00000001₍₂₎, 00000010₍₂₎, 00000011₍₂₎, …., 11111111₍₂₎ 와 같이 정렬이 된다.

따라서 일정 간격마다 Negative Feature를 database에 삽입하면 고른 분포로 database에 삽입이 된다.

Map은 Index를 사용할 수 없기 때문에 정렬된 Map 내의 Value를 Vector 컨테이너로 옮긴 후, index를 따라 일정 간격 단위로 값을 database에 저장한다.

map에서 vector로 옮기는 중에 출력된 Map의 Key값

Vector 컨테이너에서 Negative Feature를 database에 삽입하는 조건은 다음과 같다.

distanceVal = negaSize / posSize; distanceSmallVal = distanceVal / negativeMulti;

negaVector.reserve(vectorMap_Negative.size());

for (auto elem : vectorMap_Negative) negaVector.push_back(elem.second);

for (int mn = 0; mn < negativeMulti; ++mn)

for (int d = mn * distanceSmallVal; d < negaVector.size(); d += distanceVal){}

distanceVal은 negative vector가 positive vector의 몇 배인지 확인하는 변수이다. distanceSmallVal는 몇 배인지 알았을 때 negative vector를 positive의 몇 배 만큼 집어넣을지 확인해서 간격을 다시 나눠서 가지는 변수이다.

여기까지 해서 Positive feature 5,128개, Negative feature: 15,385개를 database에 삽입했다.

3. Feature classification by machine learning

1) LIBSVM

Feature 분류를 위한 라이브러리는 LIBSVM을 사용한다. MLP보다 간단하며 사용 예가 많다는 점에서 적절하다고 판단했다.

목차 2.의 모든 과정은 LIBSVM에서 사용할 적절한 DB를 만들기 위함이다. 용량이 적으면서 적절한 양을 가진 DB가 있으면 빠르게 처리할 수 있고 많은 테스트를 시도해볼 수 있다.

위에서 만든 feature database를 LIBSVM을 이용하여 Train을 하면 다음과 같은 결과와 함께 model이 완성된다.

Feature database의 Train 결과

위의 feature database를 train했을 때, 11,030 줄의 파일이 하나 생성된다.

이미지 측정을 위해서는 Predict 과정을 거쳐야 하는데, 다음과 같은 방법으로 진행하였다.

Sample에 특정 이미지에 내의 모든 LBP feature값을 기록한다. 특징점의 값은 모두 Negative 즉, 0으로 설정한다. 이러면 모든 픽셀의 LBP Pattern을 Predict를 통해 Negative인지 아닌지 측정을 하며 Negative일 경우 1, Positive일 경우 0을 출력한다. 이를 통해서 샘플 이미지에 대한 특징점을 찾아낼 수 있다.

Predict 결과 99%라는 것은 해당 이미지의 Negative가 99% 있음을 나타낸다.

4. Feature detection from test image

1) Lenna 128 x 128

빠른 시간에 테스트를 해보기 위하여 Lenna 128 x 128 이미지를 사용하였다.

비교 이미지는 SIFT를 사용하며 Train을 하기 위한 조건과 마찬가지로

if (((o + d) / 3.0)>1) 라는 조건을 설정해준다.

Predict 결과(좌측), SIFT 수정 결과(가운데), 기존 SIFT 결과(우측)

조금 당황스러운 결과가 나왔는데, 이미지가 작아서 위의 조건을 달면 Lenna 128 x128에서는 특징점이 거의 검출되지 않았다. 따라서 기존 SIFT 결과물과의 비교를 진행한다.

기존 SIFT의 결과는 특징점이 140개가 검출되었고, SVM을 통한 결과는 97개가 검출되었다. 개수는 조금 다르지만 Train할 database를 생성할 때 이미지별로 각각 100개가 안되는 Positive를 추출해서 입력했던 것을 감안하고 볼 때, 기존 SIFT보다 더 괜찮을 결과가 나왔다.

Predict 결과물은 눈을 인지하고 벽과 같은 빈 공간에 점이 배치되어 있지 않지만 SIFT 결과물은 눈을 특징점으로 인지하지 않고 죄측 상단의 벽에 적절하지 못한 특징점이 존재한다.

2) Lenna 512 x 512

Predict 결과(좌측), SIFT 수정 결과(가운데), 기존 SIFT 결과(우측)

Lenna 512 x 512에서 재밌는 결과가 나왔다. SIFT 코드를 수정한 이미지는 102개의 특징점, 기존 SIFT 코드로 나온 특징점은 2,123개, SVM으로 나온 특징점은 1,447개이다.

개수는 기존 SIFT보다 적지만 특징점의 위치가 벽면에 있는 개수가 훨씬 적고, 눈이나 다린, 머리카락 경계 등, 더욱 정확한 위치를 찾고 있는 것을 보게 된다.

3) Trained Image

Predict 결과(좌측), SIFT 수정 결과(가운데), 기존 SIFT 결과(우측)

4) Other Image

Predict 결과(좌측), SIFT 수정 결과(가운데), 기존 SIFT 결과(우측)

5. 평가

SIFT 결과보다 대체적으로 만족스러운 결과를 보여주었다. OpenCV에 내장된 SIFT와 비교를 하진 못했지만 기존에 만들었던 SIFT에 비해서 훨씬 적절한 결과를 제공해준다.

용량과 속도의 제한이 있어서 multi-core LIBLIBRARY 같은 것을 사용해보고자 했지만 정상적으로 작동하지 않아서 용량을 축소하였기에 많은 특징점을 삽입하지 못한 점은 아쉬운 점으로 남는다.

#include "stdafx.h"
#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/imgproc/imgproc.hpp>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include<iostream>
#include <string>
#include <sstream>
#include <fstream>
#include <list>
#include <vector>
#include <bitset>
#include <stdlib.h
#include <direct.h>
#include <Windows.h>
#include <map>
#include <set>
using namespace cv;
using namespace std;
#define Octave 2
#define Gaussian 6
#define siftThreshold 3

#define lbpWidth 11
#define multiWidth lbpWidth*lbpWidth
#define multiWidthExceptCenter multiWidth-1
#define border (lbpWidth-1)/2
#define getPositiveSize 5000
#define negativeMulti 3
#define setValuePositive 1

struct OctaveGroup//한 옥타브 그룹당 가지고 있는 정보 가우시안 필터, DoG 채널, 키포인트
{
	Mat gaussianFliter[Gaussian];//한 옥타브 당 가지고 있는 Gaussian Filter
	Mat DoGChannel[Gaussian - 1];//한 옥타브 당 가지고 있는 DoG Channel은 Gaussian-1개.
};
//SIFT용 함수
int CheckSigSize(double sig)//Sig를 이용하여 값을 계산해야 Size를 계산해야 되는데 빈번하게 쓰여서 따로 함수를 묶음.
{
	int size;//출력할 마스크 사이즈

	size = ceil(6 * sig);//6*sig에 올림수를 마스크 사이즈로 임시 설정

	if (size % 2 == 0)//만약 짝수일 경우
		size++;//1을 더함

	return size;//마스크 사이즈 return;
}
typedef struct int256
{
	__int64 a = 0;
	__int64 b = 0;
	__int64 c = 0;
	__int64 d = 0;
	bool operator < (const int256 &rhs) const
	{
		if (d != rhs.d)
			return (d < rhs.d);
		if (c != rhs.c)
			return (c< rhs.c);
		if (a != rhs.a)
			return (a < rhs.a);
		return (a < rhs.a);
		/*
		if (a != rhs.a)
			return (a < rhs.a);
		if (b != rhs.b)
			return (b< rhs.b);
		if (c != rhs.c)
			return (c < rhs.c);
		return (d < rhs.d);
		*/
	}
};
typedef struct groupMaxWidth
{
	int *t = new int[multiWidth];
};
int backData(int n)
{

	return 1 * pow(2, n) + backData(n - 1);
}

int main()
{
	String fileName = "lbp11x11_g4o1_image500_LastTest_2.t";
	vector<String> fileList;
	int allPositive = 0;
	int allNegative = 0;
	for (int i = 1; i <= 500; ++i)
	{
		string t = "c:/image/";
		t += to_string(i);
		t += ".jpg";
		fileList.push_back(t);
	}
	printf("Image List Count: %d lbpWidth: %d x %d\n", fileList.size(), lbpWidth, lbpWidth);
	map<int256, bitset<multiWidth>>vectorMap_Positive;
	map<int256, bitset<multiWidth>>vectorMap_Negative;

	for (int fl = 0; fl < fileList.size(); ++fl)
	{
		clock_t st = clock();
		//이미지 로드
		OctaveGroup octave[Octave];//개수에 따른 Octave 생성.

		Mat image = imread(fileList[fl]);//이미지 보관.
		Mat gray;//grayscale 이미지를 저장할 Mat
		Mat gray_pad;

		cvtColor(image, gray, CV_BGR2GRAY);//grayscale 이미지 사용.
		int *imageResult = new int[image.cols * image.rows];
		memset(imageResult, 0, sizeof(int)*image.cols * image.rows);//Train용
		//memset(imageResult, 1, sizeof(int)*image.cols * image.rows);//Predict용
		copyMakeBorder(gray, gray_pad, border, border, border, border, BORDER_CONSTANT, Scalar(0));//제로 패딩
		printf("Current Image Number: %d lbpSize: %d x %d\n", fl + 1, lbpWidth, lbpWidth);//c는 픽셀의 개수
		double beforeSig;//이전 Sig와의 비교를 이용하여 sqrt(sig_n+1^2 - sig_n^2)를 구하기 위한 용도.

		for (int i = 0; i < Octave; ++i)
		{
			for (int j = 0; j < Gaussian; ++j)
			{
				double sig;
				int size;

				if (j == 0)//첫 가우시안 필터일 경우.
				{
					if (i != 0)//0옥타브가 아닐 경우
					{
						pyrDown(octave[i - 1].gaussianFliter[3], octave[i].gaussianFliter[j],
							Size(octave[i - 1].gaussianFliter[3].cols / 2, octave[i - 1].gaussianFliter[3].rows / 2));//이전 옥타브의 4번째 이미지를 축소하여 가져온다.
						beforeSig = 1.6;//Sig는 1.6이었던 것으로 가정.
					}
					else//0 옥타브일 경우, 원본 이미지에 sig 1.6 값을 이용하여 필터링.
					{
						sig = 1.6;//첫번째 이미지는 Sig가 1.6.
						size = CheckSigSize(sig);//Sig 값에 따른 마스크 사이즈 확인
						GaussianBlur(gray, octave[i].gaussianFliter[j], Size(size, size), sig, sig);//가우시안 블러.
						beforeSig = sig;//Sig 기록
					}
				}
				else
				{
					sig = beforeSig * pow(2.0, 1.0 / 3.0);//Sig_n+1 = Sig_n * k.   k = 2^(1/3)에 대한 코드
					double currentSig = sqrt(pow(sig, 2) - pow(beforeSig, 2));//sqrt(Sig_n+1^2 - Sig_n^2)에 대한 코드.
					size = CheckSigSize(currentSig);//Sig 값에 따른 마스크 사이즈 확인
					GaussianBlur(octave[i].gaussianFliter[j - 1], octave[i].gaussianFliter[j], Size(size, size), currentSig, currentSig);//이전 가우시안 필터를 기반으로 한 가우시안 블러.
					beforeSig = sig;//Sig 기록
				}
			}
		}
		for (int i = 0; i < Octave; ++i)//모든 옥타브에서 처리.
		{
			for (int j = 0; j < Gaussian - 1; ++j)//DoG 채널의 개수는 Gaussian - 1
			{
				//octave[i].DoGChannel[j] = octave[i].gaussianFliter[j + 1] - octave[i].gaussianFliter[j];
				absdiff(octave[i].gaussianFliter[j + 1], octave[i].gaussianFliter[j], octave[i].DoGChannel[j]);
			}
		}


		int pp = 0;
		for (int o = 0; o < Octave; ++o)//모든 옥타브에서 실행.
		{//1,2,3 //0, 1    => 3, 1
			for (int d = 1; d < Gaussian - 2; ++d)//DoG를 비교할 때, 0번째와 맨 마지막은 사용하지 않는다. DoG개수는 Gaussian-1이므로 Gaussian-2로 설정
			{
				for (int i = 1; i < octave[o].DoGChannel[d].rows - 1; ++i)//첫 열과 끝 열, 첫 행과 끝 행은 기준으로 삼지 않는다. 옥타브마다 rows, cols값이 다르다.
				{
					for (int j = 1; j < octave[o].DoGChannel[d].cols - 1; ++j)
					{
						int neighbor[26];//26개의 이웃값을 삽입할 배열
						int n = 0;//배열 번호.
						int value = octave[o].DoGChannel[d].at<uchar>(i, j);//현재 기준의 값.

						for (int t = -1; t <= 1; ++t)//26개는 각각 채널별로 3x3 공간의 값을 받아온다. 자신을 기준으로 -1부터 +1까지의 값을 받아오므로 다음과 같은 for문으로 대입.
						{
							for (int tt = -1; tt <= 1; ++tt)
							{
								neighbor[n++] = octave[o].DoGChannel[d - 1].at<uchar>(i + t, j + tt);//기준 위치보다 상위 DoG채널의 값 받아오기.
								neighbor[n++] = octave[o].DoGChannel[d + 1].at<uchar>(i + t, j + tt);//기준 위치보다 하위 DoG채널의 값 받아오기.
								if (t != 0 || tt != 0)//기준과 같은 위치의 값은 배열에 넣지 않는다.
								{
									neighbor[n++] = octave[o].DoGChannel[d].at<uchar>(i + t, j + tt);//기준 DoG채널의 값 받아오기
								}
							}
						}
						int max = neighbor[0];//max, min에 초기값으로 첫 neighbor값 삽입.
						int min = neighbor[0];

						for (int x = 1; x < 26; ++x)//min, max 비교
						{
							if (max < neighbor[x])
							{
								max = neighbor[x];
							}
							else if (min > neighbor[x])
							{
								min = neighbor[x];
							}
						}
						if ((value > max || value < min))//&& 1.6*pow(2, (o + d) / 3.0) > siftThreshold)//극정이면서 임계값을 넘어가는 경우
						{
							if ( ((o + d) / 3.0)>1)
							{
								int it = i * pow(2, o);
								int jt = j * pow(2, o);
								imageResult[it *image.cols + jt] = setValuePositive;
								pp++;
							}
						}
					}
				}
			}
		}//기존 과제2번에서 약간을 수정을 거침.

		int beforeP = vectorMap_Positive.size();
		int beforeN = vectorMap_Negative.size();

		cout << "get vector SIFT   "<< endl;
		int p = 0;
		int n = 0;
		int beforeMapP = vectorMap_Positive.size();
		int beforeMapN = vectorMap_Negative.size();
		
		for (int imager = border; imager < image.rows - border; imager++)
		{
			for (int imagec = border; imagec < image.cols - border; imagec++)
			{
				bitset<multiWidth> tempbit;
				tempbit[0] = imageResult[imager * image.cols + imagec];
				int tempbitNum = 1;
				uchar center = gray.at<uchar>(imager, imagec);

				for (int y = 0; y < lbpWidth; ++y)
				{
					for (int x = 0; x < lbpWidth; ++x)
					{
						if (y != border || x != border)
						{
							tempbit[tempbitNum] = (center > gray.at<uchar>(imager + y - border, imagec + x - border)) ? 1 : 0;
							tempbitNum++;
						}
					}
				}
				if ((int)tempbit[0] == 1)
				{
					{
						int256 key;
						if (multiWidth <= 64)
						{
							for (int i = 0; i < multiWidth; ++i)
							{
								if ((int)tempbit[i] == 1)
								{
									key.d += pow(2, i);
								}
							}
							allPositive++;
							//vectorMap_Positive.insert(std::make_pair(std::make_pair(0, 0), 1));
							vectorMap_Positive.insert(pair<int256, bitset<multiWidth>>(key, tempbit));
							//vectorMap_Positive.insert(pair<int256, bitset<multiWidth>>(key, tempbit));
						}
						else
						{

							for (int i = 0; i < 64; ++i)
							{
								if ((int)tempbit[i] == 1)
								{
									key.d += pow(2, i);
								}
							}
							for (int i = 0; i < multiWidth - 64; ++i)
							{
								if ((int)tempbit[64 + i] == 1)
								{
									key.c += pow(2, i);
								}
							}
							for (int i = 0; i < multiWidth - 128; ++i)
							{
								if ((int)tempbit[128 + i] == 1)
								{
									key.b += pow(2, i);
								}
							}
							for (int i = 0; i < multiWidth - 192; ++i)
							{
								if ((int)tempbit[192 + i] == 1)
								{
									key.a += pow(2, i);
								}
							}
							allPositive++;
							vectorMap_Positive.insert(pair<int256, bitset<multiWidth>>(key, tempbit));
							p++;
						}
					}

				}
				else
				{
					{
						int256 key;
						if (multiWidth < 64)
						{
							for (int i = 0; i < multiWidth; ++i)
							{
								if ((int)tempbit[i] == 1)
								{
									key.d += pow(2, i);
								}
							}
							allNegative++;
							vectorMap_Negative.insert(pair<int256, bitset<multiWidth>>(key, tempbit));
						}
						else
						{

							for (int i = 0; i < 64; ++i)
							{
								if ((int)tempbit[i] == 1)
								{
									key.d += pow(2, i);
								}
							}
							for (int i = 0; i < multiWidth - 64; ++i)
							{
								if ((int)tempbit[64 + i] == 1)
								{
									key.c += pow(2, i);
								}
							}
							for (int i = 0; i < multiWidth - 128; ++i)
							{
								if ((int)tempbit[128 + i] == 1)
								{
									key.b += pow(2, i);
								}
							}
							for (int i = 0; i < multiWidth - 192; ++i)
							{
								if ((int)tempbit[192 + i] == 1)
								{
									key.a += pow(2, i);
								}
							}
							allNegative++;
							vectorMap_Negative.insert(pair<int256, bitset<multiWidth>>(key, tempbit));
							n++;
						}
					}
				}

			}
		}
		cout << "Finded Positive: " << p << " Finded Negative: " << n << endl;
		cout << "Collapsed Positive: " << p - (vectorMap_Positive.size() - beforeMapP) << " Collapsed Negative: " << n - (vectorMap_Negative.size() - beforeMapN) << endl;
		cout << "current Positive List:" << vectorMap_Positive.size() << " Negative List: " << vectorMap_Negative.size() << endl;
		clock_t ed = clock();
		printf("Elapsed time = %u ms\n\n", ed - st);
	}
	cout << "Found Positive: " << allPositive << "   Found Negative: " << allNegative;
	printf("All Positive: %d All Negative: %d\n", vectorMap_Positive.size(), vectorMap_Negative.size());

	ofstream out(fileName);


	//아래는 단순 삽입 부분. 건드리지 말자.
	//map<int256, bitset<multiWidth>>::iterator iter;
	//iter = vectorMap_Positive.begin();
	vector<bitset<multiWidth>>posiVector;
	posiVector.reserve(vectorMap_Positive.size());
	for (auto elem : vectorMap_Positive)
	{ 
		cout << elem.first.a << " " << elem.first.b << " " << elem.first.c << " " << elem.first.d << endl; //이미지용
		posiVector.push_back(elem.second);
	}
	printf("moved from map to Positive vector\n");
	int insertP = 0;
	int distanceP = 1;
	//if (getPositiveSize != 0)
	//	distanceP = posiVector.size() / getPositiveSize;
	for (int d = 0; d<posiVector.size();d+=distanceP)
	{
		out << "1" << " ";
		for (int j = 1; j < multiWidth - 1; ++j)
		{
			if (posiVector[d][j] == 1)
			{
				out << j << ":";
				out << posiVector[d][j] << " ";
			}
		}
		out << multiWidth - 1 << ":";
		out << posiVector[d][multiWidth - 1] << " ";
		out << "\n";
		insertP++;
	}

	printf("Inserted Positive: %d\n", insertP);
	int posSize = insertP;
	int negaSize = vectorMap_Negative.size();
	int distanceVal = 1;
	int distanceSmallVal =0;
	//if (getPositiveSize != 0)
	//{
		distanceVal = negaSize / posSize;
		distanceSmallVal = distanceVal / negativeMulti;
	//}
	int insertN = 0;

	vector<bitset<multiWidth>> negaVector;
	negaVector.reserve(vectorMap_Negative.size());

	for (auto elem : vectorMap_Negative)
	{
		negaVector.push_back(elem.second);
	}
	printf("moved from map to Negative vector\n");
	for (int mn = 0; mn < negativeMulti; ++mn)
	{
		for (int d = mn * distanceSmallVal; d < negaVector.size(); d += distanceVal)
		{
			out << "0" << " ";
			for (int bit = 1; bit < multiWidth-1; ++bit)
			{
				if ((int)negaVector[d][bit] == 1)
				{
					out << bit << ":";
					out << negaVector[d][bit] << " ";
				}
			}
			out << multiWidth - 1 << ":";
			out << negaVector[d][multiWidth - 1] << " ";
			out << "\n";
			insertN++;
		}
	}
	cout << "complete Inserted P: " << insertP << " Inserted N: " << insertN << endl;
	out.close();
	return 0;
}

https://www.mixamo.com/

http://markov.tistory.com/

2007년 이후로 글이 없는데 상당히 도움이 된다.