THE CURVE SHORTENING PROBLEM
1 1 SHAPE RECOGNITION DETERMINING AUTOMATICALLY THE NATURE OF A DETECTED OBJECT IS IT A MAN A VEHICLE WHAT KIND OF VEHICLE ETC IS ACHIEVED BY PLACING IT IN SOME PRE ESTABLISHED CLAS SI CATION WHICH IS THE PRELIMINARY KNOWLEDGE ALGORITHMS USE SOME MORE OR LESS LARGE DATABASES ALLOWING TO PRECISE THE CLASSI CATION AND TRY TO COMPARE THE DETECTED SHAPES WITH KNOWN ONES SHAPE RECOGNITION IS THIS CLASSI CATION OTHERWISE SAID WE HAVE A COLLECTION OF MODEL PATTERNS AND WE WANT TO KNOW WHICH ONE THE DETECTED SHAPE MATCHES BEST A MORE SIMPLE SUBPROBLEM IS TO DECIDE WHETHER THE OBSERVED SHAPE MATCHES A GIVEN MODEL THIS RAISES AT LEAST TWO QUESTIONS 1 WHAT KIND OF REPRESENTATION DO WE TAKE FOR A SHAPE OR WHAT IS OUR MODEL OF 2 WHAT KIND OF PROPERTIES A SHAPE RECOGNITION ALGORITHM SHOULD SATISFY IN WHAT FOLLOWS WE ONLY CONSIDER TWO DIMENSIONAL IMAGES THE ANSWER TO THE RST QUESTION SHALL BE SIMPLE A SHAPE WILL BE A SUBSET OF THE PLANE IF THE SET IS REGULAR IT SHALL BE USEFUL TO REPRESENT IT BY ITS BOUNDARY IF THE SET IS BOUNDED ITS BOUNDARY IS A CLOSED CURVE BY THE THEOREM OF ALEXANDROV 2 4 IT IS EQUIVALENT TO KNOW THE SET OR ITS BOUNDARY IN ORDER TO ANSWER THE SECOND QUESTION LET US FOLLOW DAVID MARR IN VISION AT ALL ON THE VIEW POINT THIS IN TURN MEANS THAT THE PIECES AND ARTICULATION OF A SHAPE NEED TO BE DESCRIBED NOT RELATIVE TO THE VIEWER BUT RELATIVE TO A FRAME OF REFERENCE BASED ON THE SHAPE ITSELF THIS HAS THE FASCINATING IMPLICATION THAT A CANONICAL COORDINATE FRAME MUST BE SET UP WITHIN THE OBJECT BEFORE ITS SHAPE IS DESCRIBED AND THERE SEEMS TO BE NO WAY OF AVOIDING A CANONICAL COORDINATE FRAME IS A COORDINATE FRAME UNIQUELY DETERMINED BY THE SHAPE ITSELF THE DESCRIPTION MUST BE STABLE IN THE SENSE THAT IT MUST BE INSENSITIVE TO NOISE FOR INSTANCE CONSIDER THE SHAPE GIVEN BY THE CURVE ON FIG 1 2 A THIS CURVE HAS BEEN OBTAINED BY SCANNING A HAND AND THEN BY THRESHOLDING THE GREY LEVEL TO A SUITABLE VALUE ONE HAS NO DIF CULTY TO RECOGNIZE THIS SHAPE IMMEDIATELY HOWEVER IN A COMPUTATIONAL POINT OF VIEW THIS SHAPE IS VERY COMPLICATED A QUANTITATIVE MEASURE OF THIS COMPLEXITY IS THAT THE CURVE HAS ABOUT 2000 IN EXION POINTS MOST OF WHICH HAVING NO PERCEPTUAL MEANING LET US NOW CONSIDER THE SHAPE ON FIG 1 2 B THIS SHAPE HAS BEEN OBTAINED FROM THE ORIGINAL ONE BY SMOOTHING IT WITH AN ALGORITHM DESCRIBED IN THE FOLLOWING OF THESE LECTURES THE TINY OSCILLATIONS HAVE DISAPPEARED AND THE CURVE HAS ONLY 12 IN EXION POINTS IN ITSELF THIS NUMBER HAS NO ABSOLUTE SIGNI CANCE HOWEVER THIS SHAPE IS INTUITIVELY BETTER IN A COMPUTATIONAL POINT OF VIEW FOR THREE REASONS 1 IT IS VERY CLOSE TO THE RST ONE 2 IT IS SMOOTHER 3 FIG 1 2 B IS A GOOD SKETCH OF A HAND IN THE SENSE THAT IT CANNOT BE MUCH SIM PLI ED WITHOUT CHANGING THE INTERPRETATION AS A PARALLEL ATTNEAVE 15 SHOWED A SKETCH OF A CAT CONTAINING ONLY A FEW CAREFULLY CHOSEN LINES WHICH WERE SUF CIENT TO GUESS WHAT THE DRAWING WAS THIS MEANS THAT UP TO SOME POINT A SHAPE CAN BE CONSIDERABLY SIMPLI ED WITHOUT ALTERING OUR RECOGNITION IN A SENSE FIG 1 2 B IS CLOSER THAN FIG 1 2 A TO THE MINIMAL DESCRIPTION OF A HAND A ORIGINAL SHAPE B SMOOTHED SHAPE FIG 1 2 THE REPRESENTATION OF SHAPE FOR RECOGNITION MUST BE AS SIMPLE AND STABLE AS POSSIBLE BOTH SHAPES REPRESENT THE SAME OBJECT AT DIFFERENT LEVEL OF DETAILS FOR A RECOGNITION TASK MOST OF DETAILS ON FIG 1 2 A ARE SPURIOUS THE SHAPE ON FIG 1 2 B IS INTUITIVELY MUCH SIMPLER AND VISUALLY CONTAINS THE SAME INFORMATION AS THE NOISY ONE WHAT ABOUT THE CANONICAL COORDINATE FRAME MATHEMATICIANS WILL CALL SUCH A FRAME INTRINSIC IT IS NOT VERY COMPLICATED TO IMAGINE SUCH A FRAME FOR INSTANCE THE ORIGIN MAY BE TAKEN AS THE CENTER OF MASS OF THE SHAPE THEN THE PRINCIPAL DIRECTIONS GIVEN BY THE SECOND ORDER MOMENTS PROVIDE SOME INTRINSIC DIRECTIONS THOSE HAVE THE NICE ADDITIONAL PROPERTIES TO BE INVARIANT WITH RESPECT TO ROTATIONS HOWEVER IF WE THINK OF A CIRCLE THIS INTRINSIC FRAME IS NOT UNIQUELY DE NED THIS DOES NOT MATTER SINCE EACH FRAME GIVES THE SAME DESCRIPTION BUT IF WE NOW THINK OF A NOISY CIRCLE THEN THE ORIENTATION OF THE FRAME VECTOR MAY DRAMATICALLY CHANGE CONTRADICTING THE STABILITY 1 1 1 AXIOMS FOR SHAPE RECOGNITION MARR DID NOT GIVE PRECISE ANY PRACTICAL ALGORITHMS FOR SHAPE REPRESENTATION AND RECOGNITION BUT IN A SENSE HE INITIATED AN AXIOMATIC APPROACH THAT HAS BEEN PRO LONGED BY MANY PEOPLE A RECENT REVIEW WITH AXIOMATIC ARGUMENTS IS PRESENTED BY VELTKAMP AND HAGEDOORN 164 FOR THE SHAPE MATCHING PROBLEM MOST PEOPLE AGREE THAT THE MATCHING PROBLEM IS EQUIVALENT TO NDING DISTANCES BETWEEN SHAPES SEE FOR EXAMPLE THE WORKS OF TROUV E AND YOUNES 159 FIRST THE DISTANCE BETWEEN OBJECTS SHOULD BE INDEPENDENT ON THE WAY WE DESCRIBE THEM IF AN OBJECT IS A SET OF PIXELS IT SEEMS CLEAR THAT A DISTANCE TAKING AN ARBITRARY ORDER OF THE POINTS INTO ACCOUNT IS NOT SUITABLE IN THE SAME WAY FOR CURVES MATCHING THE PARAMETERIZATION SHOULD NOT IN UENCE THE MATCHING WHICH SHOULD ONLY DEPEND ON THE GEOMETRY OF THE CURVES ANOTHER PROPERTY SHALL ALSO BE A CORNERSTONE OF OUR THEORY INVARIANCE MARR UNDER STOOD THAT THE RECOGNITION SHOULD NOT DEPEND ON THE PARTICULAR POSITION OF THE VIEWER THE MATHEMATICAL FORMULATION OF INVARIANCE IS A WELL KNOWN TECHNIQUE GIVING EX TREMELY IMPORTANT RESULTS IN MANY ELDS SUCH AS THEORETICAL PHYSICS OR MECHANICS WE CONSIDER A SET OF TRANSFORMATIONS HOMEOMORPHISMS WHICH HAS IN GENERAL A GROUP STRUCTURE THIS GROUP MODELS THE SET OF MODI CATIONS OF THE SHAPE WHEN THE VIEWER MOVES IN A THREE DIMENSIONAL WORLD IMAGES ARE OBTAINED BY A PROJECTION AND SUCH A GROUP DOES NOT EXIST WE CANNOT RETRIEVE HIDDEN PARTS OF OBJECTS BY SIMPLY DEFORMING THE IMAGE TAKEN BY THE CAMERA HOWEVER FOR FAR ENOUGH OBJECTS AND SMALL DISPLACEMENTS PROJECTIVE TRANSFORMATIONS ARE A GOOD MODEL TO DESCRIBE THE MODI CATION OF THE SILHOUETTE OF THE OBJECTS SINCE THEY CORRESPOND TO THE CHANGE OF VANISHING POINTS IN A PERSPECTIVE VIEW IF WE ADD SOME ADDITIONAL HYPOTHESES ON THE POSITION OF THE VIEWER WE CAN EVEN CONSIDER A SUBGROUP OF THE PROJECTIVE GROUP IF G IS THE ADMISSIBLE GROUP OF DEFORMATIONS AND D A PSEUDO DISTANCE BETWEEN SHAPES THE INVARIANCE PROPERTY CAN BE FORMULATED BY D GA B F G D A B WHERE GA REPRESENTS THE SHAPE A DEFORMED BY G AND F G R DOES NOT DEPEND ON A AND B NOTICE THAT D IS ONLY A PSEUDO DISTANCE SINCE D GA A F G D A A 0 IN A MATHEMATICAL POINT OF VIEW IT IS NATURAL TO DE NE SHAPE MODULO A TRANSFORMA TION WHICH IS EQUIVALENT TO DE NE A DISTANCE BETWEEN THE ORBITS OF THE SHAPE UNDER THE GROUP ACTION IN SUCH A WAY A TRUE DISTANCE IS RETRIEVED INSTEAD OF A PSEUDO DISTANCE THE STABILITY MAY BE THOUGHT AS NOISE INSENSITIVITY IN 164 IT IS FORMULATED BY A SET OF FOUR PROPERTIES THE RST ONE IS STRONGLY RELATED TO INVARIANCE AND WE DO NOT GO FURTHER THE LAST THREE MAY BE INTERPRETED AS FOLLOWS WE MODIFY A SHAPE BY SOME PROCESS AND WE COMPUTE THE DISTANCE BETWEEN THE ORIGINAL SHAPE AND THE NEW ONE THEN IT SHOULD BE SMALL IN THE FOLLOWING CASES 1 BLURRING WE ADD SOME PARTS POSSIBLY IMPORTANT BUT CLOSE TO THE SHAPE 2 OCCLUSION WE HIDE A SMALL PART OF A SHAPE POSSIBLY CHANGING ITS TOPOLOGY 3 NOISE ADDITION WE ADD SMALL PARTS POSSIBLY FAR FROM THE SHAPE THIS LAST PROPERTY IS NOT AN AXIOM PROPERLY SPEAKING SINCE IT IS NOT RELATED TO THE RECOGNITION ITSELF HOWEVER WE BELIEVE THAT AN ALGORITHM WILL BE ALL THE MORE EF CIENT AND FAST IF IT MANIPULATES A SMALL AMOUNT OF DATA INTUITIVELY IT IS CERTAINLY EASIER TO DESCRIBE THE CURVE OF FIG 1 2 B THAN THE ONE OF FIG 1 2 A FOR INSTANCE WE COULD THINK OF KEEPING A SKETCH OF THE CURVE LINKING THE POINTS WITH MAXIMAL CURVATURE ON THE NOISY CURVE NEARLY ALL THE POINTS ARE MAXIMA OF CURVATURE AND THE SKETCH IS AS COMPLEX AS THE ORIGINAL CURVE 1 1 2 AND THEIR CONSEQUENCES WHAT CAN BE DEDUCED FROM THE HEURISTIC ABOVE FIRST IN ORDER TO GET INSENSITIVITY TO NOISE IT SEEMS NATURAL TO SMOOTH THE SHAPES NATURALLY WE THEN FACE THE PROBLEM WHAT KIND OF OSCILLATION CAN BE LABELLED AS NOISE OR CONTAINS REAL INFORMATION THERE IS NO ABSOLUTE ANSWER TO THIS QUESTION BUT IT SHALL ONLY DEPEND OF A SINGLE PARAMETER CALLED SCALE REPRESENTING THE TYPICAL SIZE OF WHAT WILL BE CONSIDERED AS NOISE OR THE DISTANCE AT WHICH WE OBSERVE THE SHAPE SINCE WE CANNOT CHOOSE THIS SCALE A PRIORI SMOOTHING WILL BE MULTISCALE AND SHAPE RECOGNITION WILL HAVE A SENSE AT EACH SCALE SINCE THE RECOGNITION MUST RESIST TO OCCLUSION IT SHOULD AT LEAST PARTIALLY RELY ON LOCAL FEATURES THIS IS ANOTHER ARGUMENT FOR SMOOTHING SINCE LOCAL FEATURES ARE SENSITIVE TO NOISE FOR INSTANCE COMMONLY USED ARE THE IN EXION POINTS AND THE MAXIMA OF CURVATURE SINCE THEY ARE DE NED FROM SECOND DERIVATIVES THIS IS CLEAR THAT A NOISY CURVE AS IN FIG 1 2 A IS TOTALLY UNRELIABLE 1 2 CURVE SMOOTHING WE NOW ADMIT THE PRINCIPLE THAT SHAPE RECOGNITION IS MADE POSSIBLE BY A MULTISCALE SMOOTHING PROCESS REMOVING THE NOISE AT EACH SCALE IT SEEMS THAT BY ADDING THIS STEP WE HAVE COMPLICATED THE PROBLEM INDEED WE DO NOT KNOW WHAT KIND OF SMOOTHING WE HAVE TO CHOOSE THE ONLY OBJECTIVE WE HAVE IS TO MAKE LOCAL FEATURES RELIABLE IT IS ALSO OBVIOUS THAT THE SMOOTHING HAS TO BE COMPATIBLE WITH ALL THE