Speech Transcript - OPTIMAL STRUCTURE OF MEMORY MODELS FOR LOSSLESS COMPRESSION OF BINARY IMAGE CONTOURS

0:00:13	that's one
0:00:15	um i um is and the
0:00:16	a pair of uh
0:00:18	uh
0:00:19	but subject to
0:00:21	change
0:00:23	are
0:00:24	but
0:00:25	the some
0:00:27	about
0:00:29	uh the more
0:00:30	it's
0:00:30	yeah
0:00:31	for
0:00:32	true
0:00:33	yeah
0:00:34	also
0:00:35	maybe some things about
0:00:37	uh the uh
0:00:38	modeling issues
0:00:40	i
0:00:45	start i want to go through a very quickly through the enjoyment you have an image
0:00:50	by which the what we call excel
0:00:53	uh they stay
0:00:55	on a
0:00:56	i
0:00:56	i
0:00:58	is it two
0:00:59	a is
0:01:00	and do can excel as that was sent there's
0:01:03	a
0:01:04	that time was you see you know
0:01:05	uh
0:01:06	that
0:01:07	or noted the U are
0:01:09	two
0:01:09	a so are
0:01:11	such as
0:01:12	so
0:01:13	and our goal is to
0:01:15	uh are present the contour of
0:01:17	a each
0:01:18	you go by image it has but use
0:01:20	for while
0:01:21	zeros
0:01:22	model
0:01:23	and that the ones are
0:01:24	yeah
0:01:25	for that foreground this zero a the debate
0:01:29	the court would stay in between the for foreground and background
0:01:33	if by to be contained in the foreground the cells
0:01:36	not to you want to be three
0:01:38	for you see there
0:01:40	for mean required for
0:01:41	binary image
0:01:43	they have the property that uh
0:01:45	uh
0:01:46	they have an a part which is on the big
0:01:48	so a the so from the
0:01:50	for a each has an they work on them
0:01:52	the ground
0:01:53	would be a don't to the core
0:01:56	uh
0:01:57	the the a being counted he you know
0:01:59	for one it
0:02:01	so what we can see that the
0:02:03	a binary in each and the contour for are
0:02:06	or
0:02:07	we in the same information they can be a
0:02:10	no one one mapping whatever you have one we can
0:02:13	you i the other as well
0:02:15	so called or more in a binary image is you to call or modeling a whole
0:02:28	yeah going to a first of one for the sequence of big sense you one N
0:02:33	each chi a a a it's so for an A the would be given
0:02:37	mentioned
0:02:38	like T
0:02:39	and
0:02:40	a property P of this change of excess would be that to
0:02:44	uh and and pair can see that you the it sense would be connected in eight
0:02:48	i
0:02:50	or are for the creation
0:02:52	uh which you have been
0:02:55	yeah
0:02:55	that is that
0:02:56	and the court it's of the next uh
0:02:58	uh
0:02:59	so in the for it's of the last but i G placement
0:03:02	which are a a lot of be in as one
0:03:04	one
0:03:05	set
0:03:06	except they uh
0:03:08	but zero zero so we
0:03:10	don't allow here
0:03:12	instead
0:03:13	so
0:03:13	to state
0:03:14	a things
0:03:15	we have always move
0:03:17	a but i right all the directions
0:03:19	right and north
0:03:21	so it that that are not R
0:03:24	no you if we look at all these past what three uh
0:03:28	movements months on one
0:03:30	for
0:03:31	we can see that a uh we can buy eyes
0:03:33	this
0:03:34	very is you by a number you
0:03:36	which has a they use from zero to seven
0:03:39	and the equation
0:03:41	the
0:03:41	to get
0:03:43	the court it i G from
0:03:45	uh you think about a phrase
0:03:46	a number of you
0:03:48	would be
0:03:49	but i mean
0:03:50	the course
0:03:51	i i times
0:03:52	that that five
0:03:53	or four times
0:03:55	and the same uh that for sinus
0:03:57	you of the or the G
0:03:59	and you we have that dog
0:04:01	so now we make all these uh
0:04:03	a was a kid eva
0:04:04	uh
0:04:05	mark was of five or for
0:04:07	they are going to get the allowed
0:04:09	oh zero would be
0:04:11	for for
0:04:12	well be back don't
0:04:14	uh
0:04:14	down works
0:04:16	uh then two
0:04:17	but what or and so on so all of these are allowed
0:04:24	but and this a ah a prioritisation uh
0:04:27	it does uh introduced in that
0:04:29	this segment is the
0:04:30	a few it can be cheap
0:04:32	which uh uh
0:04:34	so that the
0:04:35	we have a part their
0:04:39	that's zero seven
0:04:40	and
0:04:41	uh our final change own would be a sequence of
0:04:44	those that but
0:04:47	don't numbers
0:04:48	can be a uniquely defined by
0:04:51	is you quality so if we take a job you got uh
0:04:54	one issues of the pixels
0:04:56	but
0:04:56	that's lot
0:04:57	i T
0:04:58	we get the
0:04:59	i i to me
0:05:00	at time
0:05:02	a a a a that is a very simple because uh fashion
0:05:06	to get the job but you presentation based on that
0:05:09	uh on there
0:05:11	a now we can component that
0:05:14	we have
0:05:15	a but of the point by
0:05:17	you
0:05:18	the first position of the
0:05:19	so
0:05:21	say i'm core
0:05:22	chain
0:05:23	and then a sequence of a
0:05:25	simple
0:05:25	the change
0:05:26	sequence is now be in this set zero you know seven
0:05:29	and that would be
0:05:30	no one one correspondence to the gym you can
0:05:33	sequence of excess P
0:05:34	you want to P M
0:05:37	no i was observed that the
0:05:39	uh uh this uh uh a few might quotes are would be to D dot then and it's much more
0:05:45	a efficient two
0:05:46	introduce a new variable called the bit at T
0:05:50	might as well
0:05:50	when
0:05:51	the and cold
0:05:53	but actually D uh a my
0:05:56	simple so we have
0:05:57	but minds
0:05:58	the might as well
0:05:59	that would be
0:06:00	we that is like we take a is operation
0:06:03	uh we
0:06:04	but as the model at uh
0:06:06	subsection
0:06:07	and they they the non-negative in
0:06:12	is a uh
0:06:13	now we see that uh
0:06:15	these new numbers be tough
0:06:16	uh are also connected to the positions
0:06:19	because of each other
0:06:20	but your are uh called binary T
0:06:23	and in fact is that there is a very simple and nice the passion for getting the positions of pieces
0:06:29	the second point
0:06:30	you the position of the peaks the previous time
0:06:33	and the
0:06:33	uh
0:06:34	next to used in the box
0:06:36	and are
0:06:38	new i'm then be thirty
0:06:39	which is the partition
0:06:40	you you might change
0:06:42	where these metrics is that methods similar
0:06:45	so now i mean that a a second uh it really representation of V C of pixels
0:06:50	that the position of the first six and what addition of the second um
0:06:54	and then we have that
0:06:55	uh a chain code
0:06:56	you can be numbers in this
0:06:58	said the
0:06:59	uh
0:07:00	okay and it's in being model they we have a number this at zero one up seven
0:07:08	yeah is um
0:07:09	uh
0:07:11	to code we you discuss a now it would
0:07:14	you a are you to be seven that was that B
0:07:17	point
0:07:17	where you have to move
0:07:19	as you see they are a
0:07:21	a when T V D so we move sometimes that all
0:07:24	like here
0:07:25	sometimes
0:07:26	because sometimes
0:07:27	okay that but
0:07:28	it is what
0:07:30	well as uh
0:07:32	it's so wise
0:07:33	it
0:07:33	i Y way to represent the binary make
0:07:36	but there is also a lot and i think we how to
0:07:39	we presented
0:07:39	the the by
0:07:40	introducing
0:07:42	yeah
0:07:42	and S
0:07:43	got that P which are
0:07:46	packages are is are to those
0:07:48	so they are got three
0:07:50	use
0:07:51	the back is these be uh that this is of those at
0:07:55	so we can uh uh also discuss about the chain codes are representations or water
0:08:00	just like it is that is
0:08:02	to now we have been in the this that this points you want to and so on
0:08:06	if we translate
0:08:07	the that is by a step
0:08:10	vertically and horizontally we are going to get a like things and
0:08:13	we can discuss about change "'cause" when this describe that
0:08:18	but is interesting is that now we have to move just in for what a T V so this uh
0:08:23	but this is
0:08:24	i mean to provide a something in for it but
0:08:27	and the um
0:08:28	we see that the uh
0:08:30	length
0:08:31	of the joint code here would be
0:08:33	use a number member and we went much longer than the change a the peaks
0:08:38	do have just seven except the J
0:08:40	you would have sixteen
0:08:42	now the question is
0:08:44	which would be the best presentation which one
0:08:46	should be used for encoding
0:08:49	uh the same P and and T which is the one of the age
0:08:52	that it is and exactly the same information so
0:08:55	we have to use
0:08:56	uh which are better
0:08:57	use the best is result
0:09:01	a discussing about was so uh but that uh
0:09:04	a chain codes
0:09:06	we can do to this exactly as before
0:09:08	uh
0:09:10	that
0:09:10	female
0:09:11	chain code in the uh what if D V D for
0:09:14	where you have a
0:09:15	a very similar to the definition as a for now this numbers almost
0:09:20	a a in this a zero one two three
0:09:22	that just for values for grammar
0:09:24	and uh our
0:09:26	what the image you would be no if we want and
0:09:29	uh two D set the initial that X
0:09:31	plus the
0:09:32	yeah my one uh points from the
0:09:35	uh a change words on the task with that
0:09:38	we can two also of attention
0:09:40	uh codes by introducing these difference between galactic that one runs on
0:09:44	that would believe that it is gonna before
0:09:47	that is
0:09:47	for this is that uh uh it is that is that is not just think that
0:09:52	i whole
0:09:53	which is quite a few O T
0:09:56	are introduced there
0:09:57	later than
0:09:58	well yeah that's
0:09:59	is is that to the fast at the
0:10:02	uh you uh of you well
0:10:05	but not it's not
0:10:06	as we had before
0:10:08	yeah
0:10:09	for for that
0:10:10	a definition my
0:10:11	code we had
0:10:13	the difference between two uh
0:10:15	you my quotes
0:10:16	you
0:10:17	these
0:10:18	and you had that
0:10:19	second order
0:10:20	then memory
0:10:21	now we don't have any more a second order memory more in fact we have a model with the
0:10:25	uh you put a very long memory
0:10:28	uh because now introduce to state variables
0:10:31	which i we to tell if
0:10:33	the sense of
0:10:34	a movement or along the horizontal vertical direction
0:10:38	uh
0:10:38	i get or not so he's are state that
0:10:41	that would be to state tiger was
0:10:43	and the code itself would be defined as
0:10:46	uh is you know in that is no change direction
0:10:48	why if there is a change that but but you that
0:10:51	well sense
0:10:52	whatever whatever moved that direction
0:10:54	and the call to would be one you change point detection and the sense
0:10:58	no that direction
0:11:01	so this would be a very uh
0:11:03	lot of memory of the nation and i for now we had a have to say but
0:11:08	and what of be
0:11:09	chain code then what is the next
0:11:11	that that's in the chain of and
0:11:13	sequence of
0:11:14	your these
0:11:15	uh
0:11:17	yeah a representation for is very simple going to with that we have the corporate along that the they sounds
0:11:25	there
0:11:26	thirty seven cents
0:11:27	and the colours are in the set that zero one to
0:11:30	up to seven
0:11:31	and and you have also the called uh
0:11:34	a i the got yeah images
0:11:37	and
0:11:37	you see this sequence of uh
0:11:41	simple in the
0:11:42	a a T a but as you one and two
0:11:45	uh we have a much more C press of that this is a you T all of them
0:11:49	combat to thirty seven
0:11:51	except
0:11:52	and that may say that probably this is less efficient cool
0:11:55	but is not
0:11:57	and right as in is that uh
0:11:59	we have a few force what but they are just zero one and two
0:12:03	but a more uh uh what is more interesting is that the simple to
0:12:07	we you know
0:12:07	change
0:12:08	direction and sense
0:12:11	but you is that we sell them in the scene
0:12:13	so basically they we we have
0:12:16	to see then it to see what it should get most of the time
0:12:19	and uh
0:12:22	this would be a
0:12:23	but it should be able
0:12:27	what would be to for uh why we are to see this this the compression problem
0:12:32	uh uh because the
0:12:34	uh
0:12:35	you may want think one by reading is and then would be important
0:12:38	so
0:12:40	but may also can here
0:12:42	a very good statistical models
0:12:44	object
0:12:45	we can
0:12:45	call this
0:12:46	features
0:12:47	objects
0:12:48	for a a recognition
0:12:50	and main wants to know what is the minimum description length for
0:12:53	uh
0:12:54	this models
0:12:55	so for that reason
0:12:56	we are interested in the most that's compression of the contours and that's who the study with need in this
0:13:01	the they
0:13:03	well so there is not but um which is but yeah well what did but is not identical is that
0:13:08	notation
0:13:09	contours in image segmentation and image segmentation also
0:13:12	a very important the uh a region and you do we need other
0:13:16	you
0:13:20	what is the state of that the of corporation of four chain codes
0:13:24	uh how how a codes have been used to the twenty years ago um
0:13:28	they are a fixed
0:13:29	uh
0:13:30	codes
0:13:31	defining a simple was for the for a the extensions for who but that was uh used the five years
0:13:37	ago
0:13:38	a a able to variable able uh coding run it's building that
0:13:41	also use
0:13:43	uh a what was used in a very nice paper in two thousand six but the recognition was uh a
0:13:48	or text these for
0:13:50	this code
0:13:51	the
0:13:51	you might
0:13:53	and that was used for map uh
0:13:55	what of mess
0:13:57	they have a C are they are they specific or
0:14:02	uh a lot of this i i think of it to um
0:14:06	conflicting here
0:14:08	a results
0:14:09	not i is this is it telling you should use this uh uh them a the back pages follow
0:14:15	like to publish and you what
0:14:16	the best these definition
0:14:18	if a code
0:14:20	the conclusion in this paper would be that
0:14:22	this is not the best is second best but the the best but would be in that a a three
0:14:26	T which
0:14:27	is more
0:14:28	that's one reason why it was not start it so well not
0:14:33	so the question would be what is the best
0:14:35	the should should more than four
0:14:37	or the modeling
0:14:39	we that was something in important this type
0:14:41	conditional probabilities what would be that the probability of
0:14:45	the key even all that D
0:14:47	the previous moment
0:14:49	and we have the same for big so and here for but
0:14:52	so our goal is to a which of these is that
0:14:55	better suited for our
0:14:57	one want to
0:14:58	a
0:14:59	a
0:15:01	uh i our um
0:15:03	first for the second are model we we have just introduced at these few my codes and iteration not well
0:15:09	but in our paper but we are we can get
0:15:12	also a a higher order models
0:15:13	what you combine these first order and second order models
0:15:17	uh in
0:15:18	uh
0:15:19	my model so
0:15:21	memory
0:15:22	a which use a fixed but next memory
0:15:25	or or you models where the memory of the model depends on a
0:15:32	so we have a or or just uh compressing a the point two
0:15:36	for is the
0:15:38	that's pretty
0:15:39	oh time series is then
0:15:40	we product working
0:15:41	to you should use in the decoding and have a
0:15:46	this is a um
0:15:48	need to um is that three where we have a
0:15:50	on the route
0:15:51	or one on the
0:15:52	nodes
0:15:53	the nodes
0:15:54	we have
0:15:54	deviations
0:15:55	oh
0:15:57	we have to an estimate notes that was a channel
0:15:59	uh they can either or distribution
0:16:02	that was which are thirteen
0:16:03	they are used
0:16:04	ooh
0:16:05	when whenever code so we joined the distribution quality
0:16:08	these note
0:16:09	now
0:16:10	when it would coding
0:16:11	in a lot of this court
0:16:13	so this kind of a a context you recorded data
0:16:16	we context the
0:16:18	i i assume is not uh
0:16:20	what did you are but they do find and you that of the digital
0:16:23	uh a a a a base the T but uh
0:16:26	not is pulling
0:16:28	it was
0:16:29	less uh
0:16:30	uh uh use how they it the the the coding is that paper mission
0:16:34	by a a over and the from
0:16:36	used for depression
0:16:39	my
0:16:41	a a big problem of be how to optimize the point T structure and we have but
0:16:45	class of that i a problem uh
0:16:49	for choosing this uh
0:16:51	structure of the T that's
0:16:53	any
0:16:54	one context you
0:16:55	which is four
0:16:57	uh
0:16:57	symbols in the previous positions in the G
0:17:00	um
0:17:02	we put that the statistics of of of of the counts we do i'd made in here so
0:17:07	well the time we collect at the T V what would the code lengths at time T
0:17:12	but the index
0:17:14	but that's in that's
0:17:16	and uh
0:17:17	we are it mostly in the find a a a a a get to the and the
0:17:21	of
0:17:23	the the sequence
0:17:24	get that
0:17:27	and uh uh are study after we get to the at least i be at each node what we
0:17:31	what is the balance between coding
0:17:33	don't
0:17:34	coding to the choose
0:17:36	we just at the codes of the children or back to the bottom
0:17:40	you for be a a part and is uh
0:17:43	next year is that than the children last
0:17:46	a T
0:17:47	uh
0:17:47	because you have to encode the structure of this uh
0:17:50	a those relations
0:17:51	and whenever a this happens uh we you this you know as and that you node otherwise
0:17:58	it would be a as a uh
0:18:01	i
0:18:02	and we provide like data
0:18:03	five or or for this next uh
0:18:07	politicians
0:18:08	these calls
0:18:09	that is that i think that um
0:18:12	that and program
0:18:13	a way to
0:18:14	optimized the quantity structure
0:18:16	now we've the putting we have a a bit more
0:18:18	did you got or more more thinks to
0:18:21	study we um
0:18:23	like the statistics not only that the
0:18:26	note to and time T
0:18:28	well so we take all the possible groupings of E
0:18:31	children
0:18:32	a second no
0:18:33	and and a complete the
0:18:35	such a a a code
0:18:37	oh that is
0:18:38	because the same so
0:18:40	choosing which two
0:18:42	to use would be the uh
0:18:44	a a class the lucky
0:18:46	which is now
0:18:49	we can do that
0:18:50	uh
0:18:51	structure of the three
0:18:53	so that is a a set to me a a a a are adapted the
0:18:57	a we encode
0:18:59	first thing for the structure of the T we number that is the best the at and of our change
0:19:03	all
0:19:04	and then we just we that uh chain code the with a i keep statistics but this that no no
0:19:10	a
0:19:11	or
0:19:12	two show some results
0:19:14	but that we have this a set of the what high by use only when B are shown here
0:19:18	that a very different from you you know like to make it to you know but
0:19:23	a a some images is making many holes
0:19:26	uh i think you're
0:19:28	going
0:19:29	we can
0:19:30	everything think there which uh
0:19:32	would be equivalent to a won't the full binary
0:19:35	one example is this uh a set in each
0:19:38	and you can see what is that the optimal structure of the P
0:19:42	for a
0:19:43	uh you T change go
0:19:45	and that would be to what the most structure forty uh to finish if you michael
0:19:51	this uh
0:19:52	uh uh if it should if you might what would have just a five song
0:19:55	the
0:19:56	for i
0:19:56	simple this one seven
0:19:58	something to hide that
0:20:03	the structure of the fee
0:20:06	is you more interesting if you represent dramatically what would be a to "'cause" that these of this call
0:20:11	you we have the context
0:20:12	what do with the excel
0:20:15	you have the context text up with a a a guy it is
0:20:18	and you that the german because sectors are no longer for the crack them for the because
0:20:23	although the two are
0:20:24	it but and representation
0:20:26	the context and this statistical on uh a it's to and S is different in the two representation
0:20:33	maybe i'm going the desired
0:20:34	yeah the results for the one having five we had in the that sense
0:20:39	yeah a and we uh it represents in um
0:20:42	course
0:20:43	or the performance of the
0:20:45	and probably by a context C everything here
0:20:48	we different from the a chain codes
0:20:50	the that really to be as your T which is the bands
0:20:53	well yeah or so that would be the zero line
0:20:56	oh yeah as is that you can see a higher on top of these you don't my meaning that they
0:21:00	are not as efficient as the code you want the and that happens for all the five
0:21:04	the best company but is still on the uh
0:21:07	yeah a is the core the
0:21:10	a a month with this
0:21:12	neighbour
0:21:12	for
0:21:13	uh and
0:21:14	then um
0:21:16	blue um is there uh
0:21:18	the best the context the on T D
0:21:21	excel one
0:21:24	is
0:21:25	a that that was a is i it's of a a code by grouping
0:21:31	i this is that the the sure that is that that's which are published in a recent paper in uh
0:21:35	at
0:21:36	yeah
0:21:37	just of that since the processing
0:21:39	but that is as well as you can see here
0:21:42	i results in the context you at what is the
0:21:45	i a much better
0:21:46	a
0:21:47	tens of course and
0:21:48	a a better than
0:21:49	then the
0:21:50	this one
0:21:51	uh here what they use that you just at a few or more
0:21:55	more
0:21:57	and they established by a uh yeah you great again that the best legs for all the models would be
0:22:02	be
0:22:02	well as we have a uh
0:22:04	due to a possibility to take the longest uh one text
0:22:07	and the were used other markov model
0:22:09	and we you got but but a result
0:22:12	for
0:22:13	or T one hundred five
0:22:14	and for each individual files or
0:22:19	is that a special but is day
0:22:21	uh dependence of the possible and that's so be um
0:22:24	models
0:22:25	and as you see uh our T models
0:22:29	such a some points so at this point you may say that this they
0:22:32	what they're six
0:22:33	get the best performance
0:22:35	uh a of the models
0:22:37	so this the same that additional
0:22:38	it happens us by the same or
0:22:40	the same plane
0:22:43	as got images
0:22:45	we have many presentations ah a a of the contour data are uh we found that a statistical efficiency of
0:22:51	in E papers right but
0:22:53	change
0:22:54	and the uh when we have when we use uh a T context modeling for a
0:22:59	uh that is a significant difference between the trees for one in which what D image
0:23:04	so
0:23:05	for that we said that
0:23:06	but that we use in adaptive
0:23:07	but for
0:23:09	uh i think of
0:23:10	and what we see find it that the what we we won't and is not only
0:23:15	yeah uh important point coding but is also for a find good this kid of uh
0:23:20	binary images
0:23:22	i you the
0:23:29	i i i i have time to ask some session
0:23:32	for for a i
0:23:35	yeah
0:23:36	i ask
0:23:37	i
0:23:37	that's
0:23:38	i yeah about

OPTIMAL STRUCTURE OF MEMORY MODELS FOR LOSSLESS COMPRESSION OF BINARY IMAGE CONTOURS

Image Coding

Presented by: Ioan Tabus, Author(s): Ioan Tabus, Septimia Sarbu, Tampere University of Technology, Finland