안녕하세요 업글입니다! 이번 포스팅에서는 속도 최적화한 메디안필터에 대해서 설명드리겠습니다.
메디안 필터에 대한 설명
메디안 필터에 대해서 잘 모르시는 분은 아래의 메디안필터 포스팅을 통해서 메디안필터에 대한 상세 설명을 확인하실수 있습니다.
2020/12/14 - [분류 전체보기] - c언어/c++ 메디안필터
c언어/c++ 메디안필터
안녕하세요 업글입니다! 이번 포스팅에서는 메디안 필터에 대해서 설명드리겠습니다. 메디안필터에 대한 설명 메디안필터는 데이터가 있을 때 데이터의 실제 값을 보다 정확하게 추정하기 위
elevate-yourself.tistory.com
속도 최적화 메디안 필터에 대한 설명
일반적인 메디안 필터의 경우 메디안 필터 구간에 속하는 데이터들에 대해 정렬을 한 후 가운데에 위치하는 값을 필터의 값으로 출력하게 됩니다. 여기서 로우데이터를 새로 획득할 때마다 정렬이 필요하기 때문에 많은 연산량이 필요하게 됩니다. 다수의 정렬알고리즘에서 가장 빠른편에 속하는 퀵정렬인 경우에도 평균적으로 nlogn번의 비교가 필요하게 됩니다. 그러므로 메디안 필터의 구간의 크기가 증가할수록 연산량은 점진적으로 증가하게 됩니다.
비교 연산량을 줄이기 위해서 링크드리스트와 삽입정렬을 통해서 n번의 비교로 정렬하는 방식을 설명드리겠습니다.
링크드리스트에 대해서 모르시는분들은 구글링이나 책을 통해서 배우신 후 설명을 보시는 것을 추천드립니다.
링크드리스트를 통해서 오름차순으로 정렬된 상태를 유지하고 새로운 로우데이터가 들어올 때 첫번째 노드부터 마지막 노드까지 순차적으로 비교하여 오름차순이 되도록 새로운 로우데이터 노드를 위치시켜 연결하는 방식입니다.
글의 설명으로는 이해가 힘드니 보다 나은 이해를 위해서 그림으로 설명드리겠습니다.
아래의 그림과 같이 1, 3, 4, 5, 8 순서로 오름차순이 되어있다고 가정하겠습니다.
새로운 로우데이터가 첫번째 노드보다 작은 경우 새로운 로우데이터 노드를 기존 첫번째 노드와 연결해줍니다.
0이 들어온다고 가정하면 0은 1보다 작기 때문에 1앞에 위치해야합니다. 그러므로 0과 1을 연결해줍니다.
새로운 로우데이터가 마지막 노드보다 큰 경우 새로운 로우데이터 노드를 마지막 노드와 연결해줍니다.
9가 들어온다고 가정하면 9는 8보다 크기 때문에 8뒤에 위치해야합니다. 그러므로 8과 9를 연결해줍니다.
새로운 로우데이터가 노드와 노드의 값을 가지는 경우, 노드와 노드 사이에 위치하도록 연결해줍니다.
7이 들어온다고 가정하면 5와 8사이에 위치해야합니다. 그러므로 5와 8은 서로 연결되있던 것을 끊어주고 7과 연결해줍니다.
위의 그림들에서 보셨듯이 첫번째 노드 전, 마지막 노드 후, 노드와 노드 사이와 같이 3가지 경우가 있으며 첫번째 노드부터 마지막 노드까지 n번(메디안필터의 구간 크기)만 탐색하면 정렬할 수 있습니다.
정렬한 후에는 중간 값을 획득하기 위해서 첫번째 노드부터 n/2번만큼 노드를 이동하여 값을 가져와서 메디안 필터 값을 획득할 수 있습니다.
일반 메디안 필터와 속도 최적화 메디안 필터의 연산속도 비교
비교 시 테스트 조건은 아래와 같습니다.
- 일반 메디안 필터는 qsort함수를 통해 퀵정렬을 이용하여 진행
- clock함수를 통해서 센서 값을 10000회 입력받았을 때 시간 측정
- 메디안 필터의 구간 크기는 16, 32, 64로 각각 연산시간을 측정
위의 그림에서 보시다시피 속도 최적화 메디안 필터가 연산시간이 빠르며 메디안 필터 구간 크기가 증가할수록 일반 메디안 필터의 경우는 평균 nlogn의 비교로 인해서 점진적으로 연산시간이 증가하지만 속도 최적화 메디안 필터의 경우 n번 비교로 인해서 연산시간이 증가하긴하지만 일반 메디안필터와 같이 점진적으로 증가하지 않는 것을 확인하실 수 있습니다.
속도 최적화 메디안 필터 코드
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define FALSE (0)
#define TRUE (!FALSE)
typedef struct {
int32_t data;
uint32_t idx;
}ST_MedianData;
typedef struct {
ST_MedianData* buffer;
uint32_t length;
uint32_t currentIdx;
uint32_t centerIdx;
}ST_MedianFilter;
int32_t MedianFilterInit(ST_MedianFilter* medianFilter, uint32_t length)
{
int32_t i;
int32_t result = TRUE;
medianFilter->length = length;
medianFilter->centerIdx = length / 2;
medianFilter->currentIdx = 0;
medianFilter->buffer = (ST_MedianData*)malloc(length * sizeof(ST_MedianData));
if (medianFilter->buffer == NULL) {
result = FALSE;
}
else {
for (i = 0; i < length; i++) {
medianFilter->buffer[i].data = 0;
medianFilter->buffer[i].idx = i;
}
}
return result;
}
void MedianFilterDelete(ST_MedianFilter* medianFilter)
{
free(medianFilter->buffer);
}
int32_t Compare(const void* first, const void* second)
{
int32_t result;
if (((ST_MedianData*)first)->data > ((ST_MedianData*)second)->data) {
result = 1;
}
else if (((ST_MedianData*)first)->data < ((ST_MedianData*)second)->data) {
result = -1;
}
else {
result = 0;
}
return result;
}
int32_t MedianFilter(ST_MedianFilter* medianFilter, int32_t value)
{
int32_t i;
int32_t result;
for (i = 0; i < medianFilter->length; i++) {
if (medianFilter->buffer[i].idx == medianFilter->currentIdx) {
medianFilter->buffer[i].data = value;
}
}
medianFilter->currentIdx++;
medianFilter->currentIdx %= medianFilter->length;
qsort(medianFilter->buffer, medianFilter->length, sizeof(medianFilter->buffer[0]), Compare);
result = medianFilter->buffer[medianFilter->centerIdx].data;
return result;
}
typedef struct ST_Node{
int32_t data;
int32_t idx;
struct ST_Node* next;
struct ST_Node* prev;
}ST_Node;
typedef struct {
ST_Node* head;
size_t size;
size_t filterSize;
int32_t currentIdx;
}ST_MedianFilterList;
int32_t MedianFilterListInit(ST_MedianFilterList** list, size_t filterSize)
{
int32_t result;
*list = (ST_MedianFilterList*)malloc(sizeof(ST_MedianFilterList));
if (list == NULL) {
result = FALSE;
}
else {
(*list)->head = NULL;
(*list)->size = 0;
(*list)->filterSize = filterSize;
(*list)->currentIdx = 0;
result = TRUE;
}
return result;
}
void MedianFilterListDelete(ST_MedianFilterList* list)
{
ST_Node* temp;
ST_Node* deleteNode;
temp = list->head;
while (temp != NULL) {
deleteNode = temp;
temp = temp->next;
free(deleteNode);
}
free(list);
}
int32_t MedianFilterListPush(ST_MedianFilterList* list, int32_t data, int32_t idx)
{
int32_t result = TRUE;
ST_Node* add;
ST_Node* temp;
do {
add = (ST_Node*)malloc(sizeof(ST_Node));
if (add == NULL) {
result = FALSE;
break;
}
add->data = data;
add->idx = idx;
add->next = add->prev = NULL;
list->size++;
if (list->head == NULL) {
list->head = add;
break;
}
temp = list->head;
if (add->data <= temp->data) {
add->next = temp;
temp->prev = add;
list->head = add;
break;
}
while (temp->next != NULL) {
if (temp->data <= add->data && add->data <= temp->next->data) {
temp->next->prev = add;
add->next = temp->next;
temp->next = add;
add->prev = temp;
break;
}
temp = temp->next;
}
if (temp->next == NULL) {
temp->next = add;
add->prev = temp;
}
} while (0);
return result;
}
int32_t MedianFilterListPop(ST_MedianFilterList* list, int32_t idx)
{
int32_t result = FALSE;
ST_Node* temp;
temp = list->head;
while (temp != NULL) {
if (temp->idx == idx) {
if (temp->prev == NULL) {
temp->next->prev = NULL;
list->head = temp->next;
}
else if (temp->next == NULL) {
temp->prev->next = NULL;
}
else {
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
}
free(temp);
list->size--;
result = TRUE;
break;
}
temp = temp->next;
}
return result;
}
int32_t MedianFilterListAt(ST_MedianFilterList* list, int32_t loop) {
ST_Node* temp;
temp = list->head;
for (int32_t i = 0; i < loop; i++) {
temp = temp->next;
}
return temp->data;
}
void printList(ST_MedianFilterList* list)
{
ST_Node* temp;
temp = list->head;
while(temp != NULL){
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
temp = list->head;
while (temp != NULL) {
printf("%d ", temp->idx);
temp = temp->next;
}
printf("\n");
}
int32_t medianFilterList(ST_MedianFilterList* list, int32_t data)
{
int32_t result;
if (list->size == list->filterSize) {
MedianFilterListPop(list, list->currentIdx);
}
MedianFilterListPush(list, data, list->currentIdx);
result = MedianFilterListAt(list, (list->size / 2));
list->currentIdx++;
list->currentIdx %= list->filterSize;
return result;
}
#define LOOP_COUNT (10000)
int32_t sensorOutput[LOOP_COUNT];
int main()
{
ST_MedianFilterList* list = NULL;
ST_MedianFilter medianFilter;
int32_t filter;
clock_t start[2], end[2];
double result[2];
if (MedianFilterListInit(&list, 64) == FALSE) {
return 0;
}
if (MedianFilterInit(&medianFilter, 64) == FALSE) {
return 0;
}
for (int32_t i = 0; i < LOOP_COUNT; i++) {
sensorOutput[i] = 50 + (rand() % 21 - 10);
}
start[0] = clock();
for (int32_t i = 0; i < LOOP_COUNT; i++) {
filter = MedianFilter(&medianFilter, sensorOutput[i]);
}
end[0] = clock();
start[1] = clock();
for (int32_t i = 0; i < LOOP_COUNT; i++) {
filter = medianFilterList(list, sensorOutput[i]);
}
end[1] = clock();
printf("start[0]=%d, end[0]=%d, start[1]=%d, end[1]=%d\n", start[0], end[0], start[1], end[1]);
result[0] = double(end[0] - start[0]);
result[1] = double(end[1] - start[1]);
printf("%lf, %lf\n", result[0], result[1]);
MedianFilterListDelete(list);
MedianFilterDelete(&medianFilter);
return 0;
}해당 코드는 제가 진행한 속도 비교 코드이므로 일반적인 메디안필터와 속도 최적화 메디안필터의 연산시간을 비교하실 수 있으며 일반적인 메디안필터 및 속도 최적화 메디안필터의 코드를 사용하실 수 있습니다.
이상 속도 최적화 메디안필터에 대한 설명을 마치겠습니다.
'프로그래밍' 카테고리의 다른 글
| c언어/c++ while문 (0) | 2020.12.17 |
|---|---|
| c언어/c++ if 조건문 (0) | 2020.12.17 |
| c언어/c++ 메디안필터 (0) | 2020.12.14 |
| c언어/c++ 이동평균필터 (0) | 2020.12.13 |
| c언어/c++ 함수포인터 (0) | 2020.11.26 |