1Composition SystemsComposition SystemsS. Geman, D.F. Potter, Z. ChiS. Geman, D.F. Potter, Z. ChiPresented by Haibin LingPresented by Haibin Ling12. 2. 200312. 2. 2003ContentsContentsIntroductionIntroductionExample: OnExample: On--line Character Recognitionline Character RecognitionComposition SystemsComposition SystemsFrom MDL to Compositional MeasuresFrom MDL to Compositional MeasuresRecognition of Scenes in ImagesRecognition of Scenes in ImagesIntroductionIntroductionDefinition:Definition:Compositionality refers to the evident ability of Compositionality refers to the evident ability of humans to humans to represent entities as hierarchies of represent entities as hierarchies of partsparts, with these parts themselves being meaningful , with these parts themselves being meaningful entities, and being reusable in a nearentities, and being reusable in a near--infinite infinite assortment of meaningful combinations.assortment of meaningful combinations.Intuitions from the definitionIntuitions from the definitionTreat objects with tree structuresTreat objects with tree structuresForm objects by composition rulesForm objects by composition rulesEvaluation candidate objectsEvaluation candidate objectsWhatWhat’’s in this papers in this paperThe purpose of this paperThe purpose of this paperTo propose a mathematical formulation of To propose a mathematical formulation of compositionalitycompositionalityTree StructureTree StructureComposition RulesComposition RulesTo devise a probability on the tree structures to promote To devise a probability on the tree structures to promote groupinggroupingInspired by MDL (Minimum Description Length)Inspired by MDL (Minimum Description Length)Recursive groupingRecursive groupingFramework for recognitionFramework for recognitionForm an object set, contains all candidate objects (trees)Form an object set, contains all candidate objects (trees)Choose the candidate with the minimum code length Choose the candidate with the minimum code length (MDL)/maximum a posteriori (MAP)(MDL)/maximum a posteriori (MAP)ContentsContentsIntroductionIntroductionExample: OnExample: On--line Character Recognitionline Character RecognitionComposition SystemsComposition SystemsFrom MDL to Compositional MeasuresFrom MDL to Compositional MeasuresRecognition of Scenes in ImagesRecognition of Scenes in ImagesOnOn--Line Character RecognitionLine Character RecognitionD. Potter, S.H. Huang, X. XingD. Potter, S.H. Huang, X. Xing2Composition system of uppercase charactersComposition system of uppercase charactersObject Library Object Library ΩΩ::Each object is represented as a tree such that for each nonEach object is represented as a tree such that for each non--terminal terminal node node nnwith label with label llthere exists a composition rule under which the there exists a composition rule under which the daughters of daughters of nncan bind to form an object of type can bind to form an object of type llΩΩis the is the set of all possible objects (trees).set of all possible objects (trees).Primitives Primitives TT: : MxMMxMgrid pointsgrid pointsLabels: Labels: NN={={““AA””,,……, , ““ZZ””}}∪∪{ line, linelet, T{ line, linelet, T--junctions, Ljunctions, L--junctions, etc.}junctions, etc.}Linelets: Linelets: Composed by two primitivesComposed by two primitivesLines: Lines: Composed by a line/linelet and a primitive Composed by a line/linelet and a primitive Composed by two lines/lineletsComposed by two lines/linelets““TT””, , ““LL””junctions, etc.junctions, etc.Uppercase charactersUppercase charactersTree structure of Tree structure of ““TT””Composition Rules for Linelets and LinesComposition Rules for Linelets and LinesLineletsLineletsTwo points Two points tt11and and tt22can group to a linelet can group to a linelet if their distance is smaller than the given if their distance is smaller than the given radius threshold radius threshold rrLinesLinesComposed by a line/linelet Composed by a line/linelet λλand a point and a point t, t, ee1 1 and and ee2 2 are the two points in are the two points in λλachieve achieve the maximum distance. Point the maximum distance. Point t t can be can be grouped with grouped with λλif if ttis within the a is within the a ““boundbound””rectangle with width rectangle with width d+2ld+2land height 2and height 2ww, , where d is the distance from where d is the distance from ee11to to ee22Composed by two linesComposed by two linesλd+2lCoding and MDLCoding and MDLMDL: An optimal interpretation is an assignment MDL: An optimal interpretation is an assignment that achieves the minimum total description length.that achieves the minimum total description length.Example of bits saved of linelet compared to two Example of bits saved of linelet compared to two primitivesprimitivesCode for each type: Code for each type: loglog22LL, , LL=|=|NN|+||+|TT||Code for each point: Code for each point: 2log2log22MMCode for each primitive: Code for each primitive: loglog22LL+ 2log+ 2log22MMCode for a linelet: Code for a linelet: loglog22LL+ 2log+ 2log22M M + 2log+ 2log22((ππrr22))Bits saved:Bits saved:loglog22LL+ 2log+ 2log22M M --2log2log22((ππrr22) > 0) > 0( since ( since ππrr2 2 < < MM22))OnOn--line Character line Character --AlgorithmAlgorithmStep 1. Build object library Step 1. Build object library ΩΩThe observed primitives are recursively aggregated The observed primitives are recursively aggregated into candidate objects under the composition rules.into candidate objects under the composition rules.Some sort of pruning based on the description length Some sort of pruning based on the description length is used to reduce the size of candidate objects.is used to reduce the size of candidate objects.Step 2. Select object from the library Step 2. Select object from the library ΩΩChoose a subset of from this collection by choosing Choose a subset of from this collection by choosing successively the next best labeling (minimal successively the next best labeling (minimal description length) among those not been labeled yet, description length) among those not been labeled yet, until all the original image is entirely labeled. until all the original image is entirely labeled. Use greedy algorithm to make the process fast.Use greedy
View Full Document