In this thesis, computer generated hologram ID tag system using fast simulated annealing method is introduced. The fast simulated annealing method greatly reduces the reconstruction error rate and generation time. The reconstruction algorithm of kinoform CGH ID tag by using electrical method is newly proposed. And the experimental results from the proposed reconstruction method are shown and analyzed.
One-dimensional and two-dimensional barcode systems are most widely used as identification tag. But, because of low data storage capacity and low data security, their applications are restricted. In this thesis, the basic concept of hologram ID that improves the weakness of the previous barcode systems is proposed, and the process of generation and reconstruction of the hologram ID pattern is described.
The conventional simulated annealing methods (original simulated annealing and low-error simulated annealing methods) have been adopted and analyzed for the purpose of hologram pattern generation. But, in the case of original simulated annealing, the reconstruction error rate is saturated relatively high value of about 10%. Although low-error simulated annealing provides the reconstruction results with a lower error rates and faster generation time than one of original simulated annealing, it is still serious problem for the purpose of hologram ID tag that the generation time increases exponentially as data size of original data increases. So, a kinoform CGH generation method with fast simulated annealing is proposed and described in this thesis. By using the simulation results, fast simulated annealing method is compared with original simulated annealing and low-error simulated annealing methods. And it is verified that fast simulated annealing can greatly save the elapsed time to approach saturation region.
In this thesis, we successfully apply multilevel kinoform computer-generated hologram (CGH) patterns, which are recorded on a fine texture paper by a photo-printer, and then retrieved by a commercial digital camera and reconstructed in the computer to the original data. Generally, the recording of the kinoform CGHs is made on a photosensitive material by laser beams, and the recorded kinoform images can be in turn retrieved by a construction beam and then reconstructed optically to the original data through a Fourier Transform lens. But, in this thesis, texture recording and electrical reconstruction system is proposed for the purpose of hologram ID tag system. The concept of new scheme is described and some advantages offered by new system are explained.
The 11-level kinoform CGH are generated on our tag samples by fast simulated annealing method, and then retrieved by a commercial digital camera and reconstructed in the computer to the original data with about 4% reconstruction error rate. The low reconstruction error is accomplished by error reduction algorithm in reconstruction process. By using suitable pattern recognition and image processing, kinoform CGH tag can be read correctly. And the reconstruction error caused from external factor and damages can be reduced by using reference pattern and dummy data. The error reduction algorithm with reference pattern and dummy data are described, and their experimental results are shown and analyzed. It is shown that the original image of a fingerprint can be reconstructed at a low error rate of about 12% although nearly half of the tag data are lost.
The fast simulated annealing and reconstruction method which provide reconstruction results with low error rates and fast generation time are presented and analyzed in depth for the purpose of hologram ID system. We expect that the newly proposed methods, if they are more optimized, can further improve kinoform CGH identification tag system.
본 학위논문에서는 효율적인 홀로그램 아이디 태그 시스템을 구축하기 위해 홀로그램 생성시간을 획기적으로 단축할 수 있는 새로운 키노폼 홀로그램 생성 알고리즘과 태그 복원 시 발생하는 에러를 정정하는 복원 알고리즘을 제안하였다.
1차원 바코드와 2차원 바코드는 저용량 정보저장 매체로서 널리 이용되고 있다. 그러나 작은 정보 저장 용량과 낮은 보안성으로 인해 다양한 응용이 불가능하다. 이를 개선하기 위하여 여러 개선된 바코드 기술들이 제안되었는데, 본 논문은 기존의 1차원 및 2차원 바코드의 문제점을 보완하고 새로운 기기가 필요 없이 기존의 포토 프린터나 디지털 카메라 등을 통해 쉽게 구현될 수 있는 홀로그램 ID 태그 기술을 제안하였다.
홀로그램 패턴을 생성하기 위해서 광학 실험의 제약이 없고 원본 데이터에 제한이 없는 컴퓨터 생성 홀로그램 기술을 이용하였다. 홀로그램 기록이 용이하도록 하기 위해 세기 정보를 무시하고 위상 정보만을 채택하여 위상 홀로그램으로 표현하였다. 세기 정보를 무시함으로써 발생할 수 있는 에러를 줄이기 위해 Simulated Annealing이라는 최적화 방법을 사용하였는데, 기존의 Original Simulated Annealing를 이용해 생성한 홀로그램 패턴은, 재생 시 원본 데이터와 10%의 오류율을 가지고 그 값에서 saturation되어 더 이상 낮아지지 않았다. 또한 홀로그램 생성에 오랜 시간이 걸렸다. 오류율을 줄이기 위해 제안된 Low-error Simulated Annealing 방법을 사용하여 오류율을 0.4%로 줄일 수 있었지만 홀로그램 생성 시간은 줄일 수 없었고 데이터 사이즈가 증가 할 때 기하급수적으로 생성 시간이 증가하였다. 데이터 사이즈가 증가할수록 초기의 Cost function 값이 높았으며 데이터의 크기가 클수록 세기 정보를 잃은 픽셀의 수가 많아져 최소값을 가지기 위한 Effective phase changes가 작은 용량의 데이터보다 많았다. 즉, 같은 cost function 값을 가지더라도 데이터 사이즈가 클수록 알고리즘 반복하여 수행하는 횟수가 많아지는 것이다. 또한 데이터 사이즈의 크기가 큰 경우, 알고리즘을 한 번 반복하는 시간이 저용량 데이터의 경우보다 오래 걸린다. 이와 같은 이유로 인해, 데이터 사이즈가 증가할수록 홀로그램 생성시간이 급격하게 증가한다. 본 논문은 빠른 시간 안에 홀로그램을 생성하기 위해 Low-error Simulated Annealing을 변형한 Fast Simulated Annealing 방법을 제안하여 획기적으로 홀로그램 생성 시간을 줄일 수 있었다.
Fast Simulated Annealing 방법은 기존의 Low-error Simulated Annealing 방법과 푸리에 변환의 선형성을 이용해 구현되었다. 홀로그램 ID 태그에 저장할 원본 데이터는 하나의 픽셀이 1의 값을 가지고 나머지 픽셀이 0의 값을 가지는 데이터들의 합성으로 나타낼 수 있다. 따라서 푸리에 변환의 성형성을 이용하여, 홀로그램 ID 태그에 저장할 위상 홀로그램은 하나의 픽셀이 1의 값을 가지고 나머지 픽셀이 0의 값을 가지는 원본 데이터로부터 변환된 위상 홀로그램들의 합성으로 나타낼 수 있다. 이 성질을 이용해 Fast Simulated Annealing 방법에서는, Low-error Simulated Annealing으로 하나의 픽셀 값이 1이고 나머지 픽셀이 0의 값을 가지는 모든 경우의 원본 데이터를 낮은 에러율을 가지는 위상 홀로그램으로 변환하여 데이터 베이스에 각각 저장한 후, 홀로그램 ID 태그에 저장할 원본 데이터의 구성에 따라 데이터 베이스에 저장되어 있는 홀로그램 패턴들을 합성하여 원하는 위상 홀로그램 패턴을 생성한다. 그러나 생성된 위상 홀로그램 패턴은 11레벨보다 많은 양자화 레벨로 이루어져 있기 때문에 ID 태그로써의 응용에 부적합하다. 따라서 수많은 레벨로 이루어진 위상 홀로그램을 11레벨로 표현하기 위해, 합성된 위상 홀로그램의 하나의 픽셀 값을 11개의 양자화 레벨을 가지는 여러 개의 픽셀로 표현한다. 이에 따라 데이터의 크기가 증가하게 된다. $100\times100$ 의 원본 데이터를 FSA를 이용해 위상 홀로그램을 생성할 경우, 데이터 사이즈는 5배로 증가하게 된다. 복원 시에는, 데이터 사이즈가 5배로 증가한 ID 태그를 인식한 후 11레벨의 위상 홀로그램을 원래의 수많은 레벨을 가진 위상 홀로그램으로 변환하여 복원한다. 기존의 Original Simulated Annealing이나 Low-Error Simulated Annealing 방법에서는 반복적인 Simulated Annealing 계산으로 인해 오랜 홀로그램 생성시간이 걸렸다. Fast Simulated Annealng 방법은 미리 데이터베이스를 구축하였기 때문에 반복적인 Simulated Anneailng 계산을 수행하지 않는다. 데이터베이스 구축 시, 반복적인 Simulated Annealing을 수행하여 많은 시간이 걸리지만, 미리 구축한 데이터베이스를 이용해 데이터베이스에 저장되어 있는 위상 홀로그램 중 알맞은 위상 홀로그램들을 합성하여 원하는 위상 홀로그램을 빠른 시간에 생성할 수 있다. 데이터베이스에는 모든 경우의 위상 홀로그램이 저장되어 있기 때문에 다양한 합성이 가능하고 다양한 위상 홀로그램을 생성할 수 있다. Fast Simulated Annealing 방법을 이용해 위상 홀로그램을 생성한 결과, 원본 데이터가 $100\times100$ 의 ‘E’ 모양 이미지 일 때, 1.705 초의 생성시간을 가졌다. 25000초의 생성시간을 가지는 Low-error Simulated Annealing 방법과 비교하여 획기적으로 생성 시간을 단축하였다. ID 태그의 데이터 사이즈가 5배 증가하지만 생성시간은 약 1/14700배로 감소하였으므로 데이터 크기의 증가에 비해 생성시간이 크게 감소하였음을 알 수 있다. FSA 방법은 모든 경우의 위상 홀로그램을 저장하고 있는 데이터 베이스를 가지고 있기 때문에 큰 정보 저장 용량이 필요하다. 10K bits의 원본 데이터를 이용해 홀로그램을 생성시킬 시에, 100MB의 정보 저장 용량이 필요하다. FSA를 통해 생성시간을 획기적으로 줄일 수 있지만 용량 또한 급격히 늘어나는 단점을 지니고 있다. 하지만, 위상 홀로그램 ID 태그 시스템을 위한 응용에서는 데이터베이스의 용량보다 홀로그램 생성시간이 더욱 중요한 요소이기 때문에 홀로그램 ID 태그 시스템 응용을 위해 매우 효과적인 방법이라 생각된다.
Fast Simulated Annealing 방법은 데이터 사이즈에 따라, 데이터의 복잡도에 따라 생성시간이 변한다. 데이터 사이즈가 증가하면 합성하는 픽셀의 수가 증가하기 때문에 생성 시간이 데이터 사이즈에 비례하여 증가한다. Fast Simulated Annealing은 원본 데이터의 복잡도에 따라 생성시간이 변하는데, 복잡도란 전체 데이터 중 1의 값을 가지는 데이터 수로 1의 값이 많아짐에 따라 합성하는 위상 홀로그램 의 개수가 많아지기 때문이다. 위상 홀로그램 생성 시간은 복잡도에 비례하여 증가한다. 복잡도가 생성 시간 단축에 큰 영향을 미치는 것은 사실이지만, 복잡도가 100%일 때에도 위상 홀로그램 생성 시간은 4.532초로 Low-error Simulated Annealing 방법보다 빠른 것을 알 수 있다.
본 논문에서, 홀로그램 ID 태그 기술은 포토 프린터와 디지털 카메라로 구현되어 쉽고 빠르게 생성과 복원이 가능하다. 그러나 카메라의 해상도와 산란된 빛 및 여러 외부 요인으로 인해 홀로그램 패턴의 값이 변질될 수 있다. 또한 외부의 공격으로 인해 홀로그램 ID 태그가 찢기거나 그 정보를 손실할 수 있다. 이러한 경우, 데이터를 복원하기 위한 복원 알고리즘을 제안하였다.
홀로그램 ID 태그는 홀로그램 패턴과 파인더 패턴, 레퍼런스 패턴으로 구성되어 있는데 홀로그램 ID 태그를 정확하게 인식하기 위한 파인더 패턴과 올바른 홀로그램 데이터 값의 인식을 위해 레퍼런스 패턴을 이용하였다. 파인더 패턴을 통해 기울어진 태그를 올바르게 인식하고 레퍼런스 패턴을 이용한 에러 감소 복원 알고리즘을 통해 산란된 빛이나 외부 요인에 의해 전체적으로 변질된 홀로그램 데이터 값을 바로 잡아 복원하여 에러율을 감소시킨다. 레퍼런스 패턴을 이용한 에러 감소 알고리즘을 통해 복원한 결과, 10%의 에러율을 줄일 수 있었다. 정보가 손실된 홀로그램 ID 태그를 복원하기 위해 더미데이터를 이용한 복원 알고리즘을 제안하였다. 홀로그램 ID 태그는 푸리에 변환을 이용해 생성되었으므로 홀로그램 패턴 중 하나의 픽셀이 원본 데이터의 모든 정보를 가지고 있다. 따라서 태그 손상으로 인해 정보가 손실 되었어도 데이터를 복원할 수 있다. 하지만 원본 데이터와 같은 크기, 같은 형태를 이루어야 복원이 가능하므로 정보가 손실된 부분에 더미데이터를 더하여 준다. 복원 시, 이 더미데이터는 모든 복원 데이터의 픽셀 값에 에러로 작용한다. 따라서 가장 적합한 더미데이터 값은 0이다. 본 논문에서는 파인더 패턴을 이용한 홀로그램 ID 태그의 인식, 레퍼런스 패턴을 이용한 에러 정정, 그리고 더미데이터를 이용한 손상된 태그의 보상 알고리즘을 포함하는 홀로그램 ID 태그 시스템에 적합한 복원 알고리즘을 제안하였다. 포토 프린터와 디지털 카메라를 이용해 구현한 홀로그램 ID 태그 시스템 실험 결과, 25%의 데이터 손실 시 8.6%의 에러율을 가졌으며, 50%의 데이터 손실 시 12.5%의 에러율을 가져 제안된 복원 알고리즘을 통해 성공적인 복원이 실현 되었음을 알 수 있다.
본 연구를 통해 홀로그램 ID 태그 시스템에 적합한 Fast Simulated Annealing 방법을 이용한 홀로그램 생성 알고리즘과 낮은 에러율을 위한 복원 알고리즘을 제안하였다. 향후에는, 데이터의 복잡도가 증가하더라도 빠른 시간 내에 홀로그램 패턴을 생성할 수 있는 보다 개선된 알고리즘 연구가 필요하고, ID 태그의 국부적 변질이나 손상에 의한 에러도 개선할 수 있는 복원 알고리즘을 위한 연구가 필요하다.
