GRCNN: Graph Recognition Convolutional Neural Network for Synthesizing Programs from FlowCharts 논문 정리

Introduction

최근 이미지 생성하는대에 있어 코딩과정이 많이 줄었다.

 

프로그램 합성을 위해선 specification이 필요하다. specification의 역할은 사용자 의도를 정확하게 표현할 수 있으며 연역적 프로그램 합성에 사용된다.

사람들의 의도를 정확히 알기위해선 여러개의 프로그램을 사용할 수 있다.

 

GRCNN(Graph  Recognition  Convolutional  Neural Network)

• flow chart를 input으로 사용
• CNN으로 이미지를 분석하고 얻은 정보를 프로그램 코드에 적용하기 위해 사용
• end-to-end network :  convolution feature vector의 계산을 공유하고 에지 및 노드 정보를 동시에 예측한다.

그림은 workflow function을 보여준다.

특징

• neural networks 와 다른 기능을 가지기에 합성에 문제가 발생하는 현상(combinatorial explosion problem)을 겪지 않는다.

그림 순서

1. 고정된크기로 GRCNN에 전달해주기 위해 flow의 이미지를 resize해준다.
2. GRCNN은 모서리에 대한 인접 행렬과 노드에 대한 문자열 목록을 포함하는 그래프 정보를 생성한다.
3. 그래프 정보를 소스 코드로 컴파일한다.

정확도 결과 

• synthesize a program: 66.4%
• edges(synthesize a program): 94.1%
• nodes (synthesize a program) : 67.9%
• another dataset(textbook에서 수동변환됨): 63.3%
• edges( textbook에서 수동변환됨 ): 72.2%
• nodes ( textbook에서 수동변환됨 ) : 81.8%

논문 특징 

• 플로우 차트에서 그래프 에지와 노드 정보를 분석하는 심층 신경망이 제시 되어있다.
• 프로그램 합성을 위한 정확하고 직관적인 specification 으로 흐름도가 제시 되어있다.
• prototype 을 보여준다.

Related Work

GRCNN의 구조

dynamic programing을 통해 속도를 높인다.

Morpheus는 input과 output을 한 쌍으로 만들고 인접한 quries를 나열한다.

Sketch와 Sqlsol는 합성 문제를 logic constraints로 인코딩하고 검색 알고리즘을 최신 SMT solver에 지정합니다. 이는 SMT solvers가 효율적으로 작동할 수 있게 합니다.

여러 방법을 통해 합성과정(synthesis process)을 빠르게 진행시킨다. 단, program이 너무 커지면 복잡도와 확장성 문제가 존재한다.

synthesis알고리즘은 첫 해결책을 찾거나 제일 빠른 해결책을 찾았을 때 과정들을 끝낸다. 하지만 사용자 의도대로 되었다고 장담할 수 없다.

• 단일 심층 합성곱 신경망(Deep Convolutional Neural Network): LPRNet은 단 하나의 심층 합성곱 신경망으로 작동한다.
• 다른 작업과의 차이점: 일반적으로 다른 작업에는 특징 추출을 위한 CNN(Convolutional Neural Network)과 예측을 위한 순환 신경망(RNN, Recurrent Neural Network) 두 가지가 모두 사용된다.
• 서브넷의 수 제한: LPRNet은 이미 4개의 서브넷을 가지고 있어 GRCNN(Gated Recurrent Convolutional Neural Network)의 서브넷 수를 제한하는 데 도움된다.
• 입력 방식의 차이: GRCNN은 번호판을 직접 입력으로 사용하기보다는 다른 네트워크에서 경계가 예측된 이미지 자르기를 입력으로 사용한다.

즉, LPRNet은 단일 네트워크로 작동하며, 공간적 순서를 유지하면서 번호판의 문자를 인식하는 데 중점을 둔 모델이다. 반면, GRCNN은 이미지 자르기를 통해 입력을 받아 특징 추출 및 예측을 위해 여러 서브넷을 사용하는 방식이다.

NETWORK

INPUT : image of a flow chart

all shapes of node: 직사각형

 

이유(= all shapes of node을 직사각형으로 보는 이유)

bounding box, designing 그리고 모든 모형을 가능하게 하기위해 heuristic algorithms을 사용하 truth data를 생성한다.

모든 형태에 대한 알고리즘을 구현하려면 상당한 엔지니어링 노력이 필요하다. 그러나 경계 상자에 대한 실제 데이터가 주어지면 알고리즘은 다른 모양을 처리하기 위해 동일한 방식으로 훈련될 수 있다.

 

input flow chart는 400X200(= 높이X길이)로 resize된다. 만약 resize할 크기보다  원본 크기가 작으면 나머지 칸을 0으로 채운다.

GRCNN의 output은 edge representation을 위한 인접 행렬과 노드 내용에 대한 텍스트 목록을 포함하는 흐름도의 그래프 표현입니다.

GRCNN의 구조 - 필요해서 한 번 더 가져왔다.

GRCNN   four parts:  

• backbone  network
• edge  detection  network
• node  detection network
• node recognition network

 

backbone  network

input : Cin X H X W

TABLE1과 TABLE2의 진행 순서

* Cin = input , Cout = 위에 단계의 output을 의미

 

The source code(algorithm produces supports sequential statements and control structure)

• IF-ELSE
• WHILE loop
• DO-WHILE loop.

edge  detection  network

• 백본 네트워크에서 생성된 특징 벡터를 입력으로 사용한다.
• 순서도(flowchart)의 에지(edge) 표현을 인접 행렬(adjacency matrix) 형태로 출력한다.

 

인접 행렬의 각 요소는 다음 세 가지 값을 가질 수 있다:

1. 0: 에지가 없음 (노드 i와 노드 j 사이에 연결이 없음)
2. 1: 일반 에지 (노드 i에서 노드 j로의 일반적인 연결)
3. 2: 결정 노드의 YES 분기 (노드 i에서 노드 j로의 YES 경로)
4. 3: 결정 노드의 NO 분기 (노드 i에서 노드 j로의 NO 경로)

순서도의 노드 수는 가변적이므로, 인접 행렬을 고정된 크기로 맞추기 위해 0으로 패딩한다.

 

이 박스 순서대로 진행

output: P AD × P AD × 3 scores( 위 연구에서 PAD지정값 = 6 )

손실함수 공식

x는 입력 벡터이고 y는 대상 클래스 인덱스입니다.

node  detection network

real = 실제, predict = 예측

IOU값 0.9이상은 positive으로 판단해 양수부여한다.
IOU값 0.3미만은 negative으로 판단해 음수부여한다.

하지만 더 정확한 분석을 위해 샘플링을 실행을 진행한다.

상위 50 anchors 뽑음(조건: IOU가 0.2이상의 값)

 

Faster RCNN과의 차이(faster rcnn도 IOU사용)

1. flow chart가 비슷한 모양과 사이즈를 가지고 있어서 하나의 anchor만 사용한다.

2. flow가 겹치지 않기때문에, 순서도의 노드는 임계값을 초과하는 IoU가 있으면 동일한 그룹으로 판단한다.

node recognition network

output size: LENVOC(vocabulary size) × 1 × W

이 박스 순서대로 진행

CTC loss가 사용되었다.

CTC loss 특징

• 필기 인식이나 음성 인식과 같은 훈련 시퀀스 문제를 위한 함수이다. 
• input이 순서가 있는 시퀀스인 경우 적용된다.
• text예측에 다른 recurrent neural network(순환 신경망)가 필요하지 않다.
• 노드 인식 네트워크의 출력을 통해 직접 예측한다.
• 문장을 구성하는 단어들의 출현 가능성을 측정하여 의미 있는 패턴을 찾아내는 역할을 한다.

예측 시 output vector로부터 text를 decode하기 위해 greedy search사용한다.

 

STN( spatial transformer net work)

• node recognition network  앞에 삽입해 경계를 추가로 조정할 수 있습니다.
• 기존 convolutional architectures 에 삽입할 수 있는 네트워크로, 신경망에 feature map을 공간적으로 변환할 수 있는 기능을 제공합니다.

 

 

Train and Implementation

whole network : end-to-end

loss 값 공식

• lossedg e = loss of edge network
• lossndc = loss of  classifier
• lossndr  = loss of regressor of node detection network and node
• lossnr = loss of  node recognition network

SGD사용해 network를 학습한다. (Learning  rate = 0.02, 만약 오류가 줄면 lr도 반으로 줄어든다. The total epoch = 200.)

 

EXPERIMENT

실험환경

• 데스크톱 환경에서 진행되었음
• Geforce 1070 GPU, Intel i7 CPU, 16GB 메모리 사용
• 네트워크 모델은 PyTorch로 구현됨

테스트한 네트워크 모델들

• GRCNN: 기본 네트워크
• Separated GRCNN: 백본 네트워크를 공유하지 않음 (IV-D절 참조)
• GRCNN with ResNet: 잔차 학습(Residual Learning) 추가 (III-A절 참조)
• GRCNN with STN: 공간 변환기(Spatial Transformer Network, STN) 추가 (III-D절 참조)
• GRCNN with ResNet and STN: 잔차 학습과 공간 변환기 모두 적용

Dataset  Generation

• data sample은 flow chart image(PNG형태)와 text file을 포함한다.
• The dataset은 flow charts(노드: 3 to 6 nodes, decision: 0 to 2) 
• 알파벳의 50가지의 특징으로 부터 텍스트에 각각의 노드는 3에서 9까지의 random한 특징을 가진다. 

 

flow chart를 그릴 때

• Graphviz를 사용한다
• 200X400 = width X height
• boundaries와 edge를 포함하는 width는 1~5까지 중 랜덤하게 선택된다.
• 폰트사이즈: 20~30
• RGB color

데이터

• train: 9960개
• test: 2490개

Accuracy

참고

예측을 시행한 것

• Edge Accuracy : 94.1%
• Sequence Accuracy: 90.6%
• Nodes accuracy: 67.9%
• Graph Accuracy of GRCNN: 66.4%

Edge Accuracy 특징

• percentage of images whose edge is correctly predicted.
• adjacent matrix가 얼마나 ground truth와 똑같은지를 의미한다. 

 

Sequence Accuracy 특징

• 모든 이미지의 모든 노드 중에서 text content가 올바르게 예측된 노드의 비율이다.
• node recognition network가 individual nodes 에 대해 얼마나 잘 작동하는지를 의미한다.

Nodes accuracy 특징

• 노드가 이미지를 얼마나 잘 예측했는지에대한 지표이다.
• 도구가 전체적인 node를 얼마나 잘 예측했는지를 의미한다.

Graph Accuracy of GRCNN 특징

• edge 와 nodes가 모두 올바르게 예측된 이미지의 비율이다.

Performance

Table VI는 GRCNN(Gated Recurrent Convolutional Neural Network)과 그 하위 네트워크의 성능을 보여줍니다. 요약하면 다음과 같습니다:

GRCNN의 전체 성능

• 전체 시간 소요: 약 60 밀리초
• 성능: 다른 네트워크와 유사

하위 네트워크의 시간 소요 비율

1. 노드 탐지 네트워크:
   • 시간 소요 비율: 70.1%
   • 주요 시간 소요 부분
2. 노드 인식 네트워크:
   • 시간 소요 비율: 23.5%
3. 백본 네트워크:
   • 시간 소요 비율: 5.8%
4. 엣지 네트워크:
   • 시간 소요 비율: 1%

특징

• GRCNN 전체의 시간 소요는 약 60 밀리초입니다.
• 노드 탐지 네트워크가 전체 시간 소요의 대부분(70.1%)을 차지합니다.
• 나머지 시간 소요는 노드 인식 네트워크(23.5%), 백본 네트워크(5.8%), 엣지 네트워크(1%) 순입니다.

End-to-End  vs  Separated  Network

edges and nodes 정보는 서로 상호작용하지 않기 때문에, edges와 노드를 예측하기위해 분리된 네트워크를 고려하는 것은 당연하다. 

참고해서 논문읽기

two clones of GRCNN 차이점

network

• the node detection network and node recognition network를 사용 불가하게 만들었다.
• For the other clone,the edge detection network만 사용 불가하다.

 

trained

• 같은 dataset과 hyper parameters를 two networks로 분리해서 학습시켰다.

 

Table V and VI

• 분리된 네트워크의 accuracy and performance를 나타낸다.
• The performance는 GRCNN에 가까우므로 backbone network 계산 공유하는 것이 가능하다. 공유 함으로 써 5.8%에 달하는 시간인 3.5 milliseconds를 절약했다.
  
  

Real-world  Program  Synthesis

VI을 참고해서 결론을 본다.

GRCNN synthesizes real world programs이 잘 작동되는 지 보기 위해서, 11개의 test dataset programs을 만들었다.

Table VII 

• programs 중 70% 가 잘 예측되었다.
• edges 70% 가 잘 예측되었다.
• individual nodes가 93.6% 으로 정확히 예측되었다.

두 샘플을 을 예시로 들어 GRCNN의 input과 output을 시각적으로 입증한다.

• 첫 샘플은 3개의 최댓값 찾는 것이다.
• 두번 째 샘플은 factorial 함수이다. 

Conclusion

특징

• GRCNN은 엣지 정보와 노드 정보를 예측합니다.
• 특징 벡터의 계산을 공유할 수 있음을 보여준다.

GRCNN은 테스트 데이터 세트에서의 정확도

• GRCNN achieves: 66.4%
• edge: 94.1%
• node : 90.6%

 

THANKS TOO....

• google translation
• Chat GPT & Claude
• 버텨준 나의 정신력과 인내력