Á¤º¸°úÇÐȸ ³í¹®Áö A : ½Ã½ºÅÛ ¹× ÀÌ·Ð
Current Result Document :
ÇѱÛÁ¦¸ñ(Korean Title) |
À籸¼º°¡´É ¸Å½¬¿¡¼ O(1) ½Ã°£ º¹Àâµµ¸¦ °®´Â ÀÌÁø¿µ»ó/»çÁøÆ®¸® º¯È¯ ¾Ë°í¸®Áò |
¿µ¹®Á¦¸ñ(English Title) |
Constant Time Transformation Between Binary Images and Quadtrees on a Reconfigurable Mesh |
ÀúÀÚ(Author) |
±è¸í
ÀåÁÖ¿í
Myung Kim
Juwook Jang
|
¿ø¹®¼ö·Ïó(Citation) |
VOL 23 NO. 05 PP. 0454 ~ 0466 (1996. 05) |
Çѱ۳»¿ë (Korean Abstract) |
º» ³í¹®¿¡¼´Â À籸¼º°¡´É ¸Å½¬¿¡¼ ÀÌÁø¿µ»óÀ» »çÁøÆ®¸®·Î º¯È¯Çϰųª »çÁøÆ®¸®¸¦ ÀÌÁø¿µ»óÀ¸·Î º¹¿øÇÏ´Â ¾Ë°í¸®ÁòµéÀ» Á¦¾ÈÇÑ´Ù. »çÁøÆ®¸®·ÎÀÇ º¯È¯ ¾Ë°í¸®ÁòÀº n*n°³ÀÇ È¼Ò¸¦ °¡Áø ÀÌÁø¿µ»óÀÌ ÁÖ¾îÁ³À»¶§, À̸¦ ¼±Çü»çÁøÆ®¸®·Î º¯È¯ÇÑ ÈÄ, ±× Æ®¸®¸¦ ±¸¼ºÇÏ´Â À§Ä¡ÄÚµåµéÀ» n*n Å©±âÀÇ À籸¼º°¡´É ¸Å½¬¿¡ ¾Õ¿¡¼ºÎÅÍ Â÷·Ê·Î ÀúÀåÇÑ´Ù. ¿©±â¼ °¢ À§Ä¡ÄÚµå´Â »çÁøÆ®¸®ÀÇ ÇÑ leaf ³ëµå¸¦ ³ªÅ¸³»¸ç, preorder¼øÀ¸·Î ÀúÀåµÈ´Ù. ÀÌ ¾Ë°í¸®ÁòÀÇ Ã¹ ´Ü°è´Â »çÁøÆ®¸®ÀÇ leaf ³ëµåµéÀ» ã´Â ÀÛ¾÷À¸·Î½á, ÀÌ´Â À籸¼º°¡´É ¸Å½¬ÀÇ ¹ö½º ¿¬°á ¹æ½ÄÀ» ÀÌ¿ëÇÏ¿© ÇØ°áÇÏ¿´´Ù. ´ÙÀ½ ´Ü°è´Â leaf ³ëµåµéÀ» Àç¹èÄ¡½ÃÅ°´Â ÀÛ¾÷À¸·Î½á, ÀÌ´Â À籸¼º°¡´É ¸Å½¬¤Ò ¹ö½º ¿¬°á ¹æ½ÄÀ» ÀÌ¿ëÇÏ¿© ÇØ°áÇÏ¿´´Ù. ´ÙÀ½ ´Ü°è´Â leaf ³ëµåµéÀ» Àç¹èÄ¡½ÃÅ°´Â ÀÛ¾÷À¸·Î½á, °£´ÜÇÏ°í È¿À²ÀûÀÎ permutation±â¹ýÀ» °³¹ßÇÏ¿© ÇØ°áÇÏ¿´´Ù. ºÐ¼±µÈ leaf³ëµåµéÀ» ¸Å½¬ÀÇ ¾ÕºÎºÐÀ¸·Î ¸ð¾Æ¾ß Çϴµ¥, ÀÌ ÀÛ¾÷Àº n*n^2 Å©±âÀÇ ÀÌÂ÷¿ø À籸¼º°¡´É ¸Å½¬¸¦ ½Ã¹Ä·¹À̼ÇÇÔÀ¸·Î½á ÇØ°áÇØ¿´´Ù. À§ ¾Ë°í¸®ÁòÀ» È®ÀåÇÏ¿© »çÁøÆ®¸®¸¦ ÀÌÁø¿µ»óÀ¸·Î º¹¿øÇÏ´Â ¾Ë°í¸®Áò ¿ª½Ã ºñ½ÁÇÑ ±â¹ýÀ» ½á¼ °³¹ßÇÏ¿´´Ù. µÎ ¾Ë°í¸®Áò ¸ðµÎ n*n*n Å©±âÀÇ À籸¼º°¡´É ¸Å½¬¿¡¼ O(1)ÀÇ ½Ã°£º¹Àâµµ¸¦ °®´Â´Ù. |
¿µ¹®³»¿ë (English Abstract) |
We investigate the problem of transforming between a binary image and its quadtree representation on the reconfigurable mesh. Our quadtree building algorithm converts a given n*n binary image, which is stored on a reconfigurable mesh of size n*n*n, into a linear quadtree and places it in the low addressed processors, one location code per processor in preorder. The algorithm first identifies the maximal quadtree nodes by controlling the bus connectivity of the resonfigurable mesh. These nodes are rearranged by our simple and efficient permutation techniques. The rearranged nodes are then compacted nto the low addressed processors by simulating an n*n^2 reconfigurable mesh using an n*n*n mesh. We also present a scheme to reconstruct the original image from the linear quadtree. For an n*n binary image, both algoritzzhms run in O(1) time using n*n*n processors. |
Å°¿öµå(Keyword) |
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|